LeetCode之二：字母异位词分组-USB迷|专注于互联网分享

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; }
};

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())

字典的另一种构造方法

除了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>());//为什么不能是List<String>list = map.getOrDefault(str,new List<String>());list.add(s);//无论str是否是新的模板字符串，都需要把当前遍历的s加入字符串列表中。map.put(str, list);//这一步为什么不会放重复的键值进去。因为str是经过排序后的，所以放多少个str进去都是一样的键值。}return new ArrayList<List<String>>(map.values());
}
}

toCharArray()

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

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

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

ArrayList<List>(map.values())