Skip to content

Latest commit

 

History

History
25 lines (14 loc) · 1.35 KB

README.md

File metadata and controls

25 lines (14 loc) · 1.35 KB

方法一

可以比较每个字符串排序后的字符串,字符颠倒的字符串排序后肯定是用一个字符串

因此,使用一个map存储“排序后字符串”和“颠倒字符串集合”的映射,key的类型是string,表示排序后的字符串,value是vector<string>,表示每个“Group Anagrams”

对于每个字符串,排序后进行查找,如果找到则插入,否则向map中插入一个新的映射

假设参数字符串数组包含N个字符串,最长的字符串包含K个字符

  • 时间复杂度:O(N*K*log(K))
  • 空间复杂度:O(N*K)

方法二

同样使用一个map,但是不对字符串进行排序,因此可以提高效率,关键是如何设计key,可以使两个字符颠倒的字符串得到相同的key?

由于所有字符颠倒的字符串肯定包含相同的字符,并且每个字符的计数也相同,因此可以对26个小写字母与(题目规定了字符串的字符为小写)进行计数,对于字符串"aabc",包含2个'a',1个'b'和1个'c'。因此key可以设计成"#2#1#1#0#0...#0",这样对于字符串”abac“也会得到相同的key

假设参数字符串数组包含N个字符串,最长的字符串包含K个字符

  • 时间复杂度:O(N*K)
  • 空间复杂度:O(N*K)

参考