Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
Solution:
What are anagrams? http://en.wikipedia.org/wiki/Anagram
In short, it is a rearrangement of letter sequence of a word. Like abcd, cdba, bcda, adcb...
What's they have in common? My first thought is add up their ASCII, but that's not accurate. For example, bb and ac but they not anagrams but have the same ASCII value.
And then I found that we can sort a word, and all anagrams will have same key. abcd, cdba, bcda, and adcb will have the same key: abcd. Intuitively, we need a hash map to save values of a key.
Tips:
1. Set<T> set = hashmap.keySet().
2. char array to String: String.valueOf(char array) or new String(char array).
Solution:
What are anagrams? http://en.wikipedia.org/wiki/Anagram
In short, it is a rearrangement of letter sequence of a word. Like abcd, cdba, bcda, adcb...
What's they have in common? My first thought is add up their ASCII, but that's not accurate. For example, bb and ac but they not anagrams but have the same ASCII value.
And then I found that we can sort a word, and all anagrams will have same key. abcd, cdba, bcda, and adcb will have the same key: abcd. Intuitively, we need a hash map to save values of a key.
Tips:
1. Set<T> set = hashmap.keySet().
2. char array to String: String.valueOf(char array) or new String(char array).
public class Solution {
public ArrayList anagrams(String[] strs) {
// anagram key -> all its related anagrams
HashMap> set = new HashMap>();
for(int i = 0; i < strs.length; i++){
String key = getKey(strs[i]);
ArrayList tmp = set.containsKey(key) ? set.get(key) : new ArrayList();
tmp.add(strs[i]);
set.put(key, tmp);
}
// return string which has at least one anagram
ArrayList result = new ArrayList();
Set keys = set.keySet();
for(String key : keys){
if(set.get(key).size() > 1)
result.addAll(set.get(key));
}
return result;
}
// sorted all chars in a string as its key
public String getKey(String str){
char[] c = str.toCharArray();
Arrays.sort(c);
// Arrays.toString(char[]): "[a, b, c, d, e, f]"
// new String(char[]), String.valueOf : "abcdef"
return new String(c);
}
}
No comments:
Post a Comment