Given an array of strings, group anagrams together.
Copy Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
给一些单词,让把出现相同字符的单词放在一组。判断是否permutation除了用count map检测每个元素是否都在, 还可以用 sorting配合hash table。
Copy class Solution :
def groupAnagrams ( self , strs : List [ str ] ) -> List [ List [ str ]] :
m = collections . defaultdict ( list )
for s in strs :
# m[''.join(sorted(s))].append(s)
cnt = [ 0 ] * 26
for c in s :
cnt [ ord (c) - ord ( 'a' )] += 1
m [ tuple (cnt)]. append (s)
return m . values ()
Copy class Solution {
public List < List < String >> groupAnagrams ( String [] strs) {
Map < String , List < String >> map = new HashMap <>();
for ( String str : strs) {
char [] cs = str . toCharArray ();
Arrays . sort (cs);
String keyStr = String . valueOf (cs);
if ( map . containsKey (keyStr)) {
map . get (keyStr) . add (str);
} else {
map . put (keyStr , new ArrayList <>());
map . get (keyStr) . add (str);
}
}
List < List < String >> res = new ArrayList <>();
for ( String str : map . keySet ()) {
res . add ( map . get (str));
}
return res;
}
}
时间复杂度O(nlgn).