面试碰到这个算法:字母异位词分组

      题目:输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
      输出:
      [
         ["ate","eat","tea"],
         ["nat","tan"],
         ["bat"]
      ]

方法1:先将每个字符串进行排序,然后判断是否相等

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
		//用于计数表示是第几个元素
        unordered_map<string,int> m;
        vector<vector<string>> res;
        string temp;
        int pos=0;

		//遍历vector
        for(auto i:strs) {
            temp = i;
			//排序
            sort(temp.begin(),temp.end());
            if(m.find(temp) == m.end()) {
                vector<string> v(1,i);
                res.push_back(v);
                m[temp] = pos++;
            }
            else {
                res[m[temp]].push_back(i);
            }
        }
        return res;
    }
};

方法2:按计数分类,记录每个字符串中每个字符出现的次数,如果字母出现的次数一样则说明两个字符串是异位的

 

上一篇:05_02_leetcode_49_字母异位分词


下一篇:Codeforces 571D - Campus(并查集+线段树+DFS 序,hot tea)