首页 > 代码库 > Leetcode-Anagrams

Leetcode-Anagrams

2024-08-04 17:02:52   219人阅读

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

Note: All inputs will be in lower-case.

NOTE: the return is the list of all anagrams groups, the order does not matter, just put the words in each anagram group into the list.

Analysis:

Count the number of appearance of each char in a word, and generate a uid string like "num[0]/num[1]/....num[25]/", then use hash table to store the words that have the same uid.

Solution:

 1 public class Solution { 2     public List<String> anagrams(String[] strs) { 3         List<String> res = new LinkedList<String>(); 4         if (strs.length==0 || strs.length==1) return res; 5          6         Map<String,List<String>> resMap = new HashMap<String,List<String>>(); 7         List<String> uidList = new ArrayList<String>();  8  9         for (int i=0;i<strs.length;i++){10             String uid = getUID(strs[i]);11             if (resMap.containsKey(uid))12                 resMap.get(uid).add(strs[i]);13             else {14                 List<String> list = new LinkedList<String>();15                 list.add(strs[i]);16                 resMap.put(uid,list);17                 uidList.add(uid);18             }19         }20 21         for (int i=0;i<uidList.size();i++){22             List<String> list = resMap.get(uidList.get(i));23             if (list.size()>1) res.addAll(list);24         }25 26         return res;27     }28 29 30     public String getUID(String s){31         int[] num = new int[26];32         Arrays.fill(num,0);33         for (int i=0;i<s.length();i++){34             char temp = s.charAt(i);35             int val = temp-‘a‘;36             num[val]++;37         }38 39         String uid = "";40         for (int i=0;i<26;i++)41             uid+=Integer.toString(num[i])+"/";42 43         return uid;44 45     }46         47 }

 

Leetcode-Anagrams


联系
我们