LeetCode之二：字母异位词分组

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]

输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [“”]

输出: [[“”]]

思路

1、先构造一个哈希散列表，键是模板字符串，值是所有与模板字符串为字母互位词的字符串，所以是个字符串列表。
2、将字符串数组的字符串取出来，进行排序，为str
3、与哈希散列表的键进行比较，是字母互位词就将值，即字符串列表拿出来，将该str添加进去。
4、不是字母互位词说明该str是个新的模板字符串，也需要作为值放到哈希散列表的列表中去。

c++

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hashtable;
        for(auto s:strs){
            string key = s;
            sort(key.begin(),key.end());
            vector<string>list;
            if(hashtable.contains(key)){
                list = hashtable.find(key)->second;
            }
            list.emplace_back(s);
            hashtable[key]=list;
        }
        vector<vector<string>> ans;
        for(auto it = hashtable.begin();it!=hashtable.end();it++) ans.emplace_back(it->second);
        return ans; 
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

sort

cpp中的sort直接传入开始和结束即可。

emplace_back()

如果是嵌套的vector，无法直接通过内层的vector直接构造整个vector，而是需要用emplace_back()或者push_back()加上去。

python

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        mp = {}
        for s in strs:
            key = "".join(sorted(s))
            if key not in mp:
                mp[key] = [s]
            else:
                mp[key].append(s)
        return list(mp.values())
1
2
3
4
5
6
7
8
9
10
11
12
13
14

字典的另一种构造方法

除了dict()之外，还可以直接写{}来构造。

“”.join(sorted(s))

list的构造方法

list(mp.values())

java

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>>map = new HashMap<String, List<String>>();
        for(String s:strs){
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String str = new String(ca);
            List<String>list = map.getOrDefault(str,new ArrayList<String>());
            //为什么不能是Listlist = map.getOrDefault(str,new List());
            list.add(s);
            //无论str是否是新的模板字符串，都需要把当前遍历的s加入字符串列表中。
            map.put(str, list);
            //这一步为什么不会放重复的键值进去。因为str是经过排序后的，所以放多少个str进去都是一样的键值。
        }
        return new ArrayList<List<String>>(map.values());
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

toCharArray()

注意：char[] ca = s.toCharArray();
Arrays.sort(ca);

getOrDefault() + List<>()和ArrayList<>()的区别

getOrDefault() 方法获取指定 key 对应对 value，如果找不到 key ，则返回设置的默认值。
hashmap.getOrDefault(Object key, V defaultValue)
所以这里的代码不可以是
Listlist = map.getOrDefault(str,new List());
而一定要是
Listlist = map.getOrDefault(str,new ArrayList());
因为List<>()是一个接口，不可以被实例化。而ArrayList可以被实例化。

ArrayList(map.values())