首页 > 代码库 > [leetcode]Anagrams

[leetcode]Anagrams

2024-07-15 08:49:37   222人阅读

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

编程珠玑中的一道题，书中的解法很巧妙，我就直接搬来用了，时间空间复杂度都是O(n)

算法思路：

将每一个单词初始化，记录每个字符的个数，比如aaabca，初始化为a4b1c1。（也可以用排序做初始化，但是时间复杂度略高）

互为Anagrams的单词的初始化字符串是相同的

 1 public class Solution { 2     public List<String> anagrams(String[] strs) { 3         Map<String,List<String>> map = new HashMap<String,List<String>>(); 4         for(String s : strs){ 5             String init = initial(s); 6             if(map.get(init) == null){ 7                 List<String> list = new ArrayList<String>(); 8                 list.add(s); 9                 map.put(init,list);10             }else{11                 map.get(init).add(s);12             }13         }14         List<String> res = new ArrayList<String>();15         for(List<String> list : map.values()){16             if(list.size() > 1){17                 res.addAll(list);18             }19         }20         return res;21     }22     private String initial(String s){23         24         int[] hash = new int[26];25         26         for(char c : s.toCharArray()){27             hash[c - ‘a‘]++;28         }29         StringBuilder sb = new StringBuilder();30         for(int i = 0; i < 26; i++){31             if(hash[i] > 0){32                 sb.append((char)(‘a‘ + i ) ).append(hash[i]);33             }34         }35         return sb.toString();36     }37 }

 


联系
我们