Note: All inputs will be in lower-case.
Naive Way: My first thought was use int[26] array to store each word's information, and then use a Map to record that information, once an anagram was found, the int[26] array info will be the same with one of the map. And later I found out that two int[] with same value aren't equal in Java from this post http://stackoverflow.com/questions/2627889/java-hashmap-with-int-array. So I use an ArrayList<Integer> instead.
This algorithm takes O(n) run time and O(n) space. And one corner case I met is when strs[] = {"",""}, the result is ["",""] instead of [""]. It means the second time a particular character appearance list was met, the string must be added into the result.
public class Solution {
public List<String> anagrams(String[] strs) {
List<String> rslt = new ArrayList<String>();
Set<String> set = new HashSet<String>();
Map<List<Integer>, String> map = new HashMap<List<Integer>, String>();
for(int i = 0;i < strs.length;i++){
// record char appearance into a List<Integer>
int[] appear = new int[26];
List<Integer> list = new ArrayList<Integer>();
for(int j = 0;j < strs[i].length();j++)
appear[(int)(strs[i].charAt(j)-'a')]++;
for(int j = 0;j < appear.length;j++)
list.add(appear[j]);
// map list to string
if(!map.containsKey(list)){
map.put(list, strs[i]);
}else{
if(!set.contains(map.get(list)))
rslt.add(map.get(list));
rslt.add(strs[i]);
set.add(map.get(list));
set.add(strs[i]);
}
}
return rslt;
}
}
No comments:
Post a Comment