Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
题解:
所谓的anagrams,只若干个词,它们包含的字母的个数和种类完全一样,只是字符的顺序不一样。比如说bus,usb,sub就是一组angrams。同一组angrams具有排序后相同的特点,比如对上述三个单词按字典序排序分别得到bsu,bsu,bsu。我们用这一点判断两个单词是否是一组angrams。
题目给出一个String数组,要求找出其中所有angrams组,并把它们放在同一个list中返回。
比如给定输入[usb,tea,eat,that,bus,sub,and],应该返回输入[usb,bus,sub,tea,eat]。
利用map解这道题,其中key是单词按照字典序排序后得到的单词,value是排序后为key的单词在strs中索引。比如上述的例子里对应的map如下表所示:
key | value |
bsu | 0,4,5 |
aet | 1,2 |
ahtt | 3 |
adn | 6 |
然后遍历map,把value对应的list长度大于1的list对应的元素放入answer list中即可。
代码如下:
public class Solution {
public List<String> anagrams(String[] strs) {
HashMap<String, ArrayList<Integer>> map = new HashMap<String, ArrayList<Integer>>();
for(int i = 0;i < strs.length;i++){
String s = strs[i];
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
if(map.containsKey(key))
{
ArrayList<Integer> value = map.get(key);
value.add(i);
map.put(key, value);
}
else{
ArrayList<Integer> strings = new ArrayList<Integer>();
strings.add(i);
map.put(key, strings);
}
} List<String> answer = new ArrayList<String>(); for(Map.Entry<String, ArrayList<Integer>> entry:map.entrySet()){
ArrayList<Integer> temp = entry.getValue();
if(temp.size() > 1){
for(int i = 0;i < temp.size();i++)
answer.add(strs[temp.get(i)]);
}
} return answer;
}
}