Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
For example:
Input: | ["tea","and","ate","eat","dan"] |
Output: | ["tea","ate","eat"] |
Expected: | ["and","dan","tea","ate","eat"] |
A:
--------------------利用HashMap来保持,做到了O(n)的效率------------------------
public class Solution { public ArrayList<String> anagrams(String[] strs) { // using method to siulate O(n) method ,assume string length is constant ArrayList<String> al = new ArrayList<String>(); if(strs == null) return al; HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>(); for(String str : strs){ char [] chars = str.toCharArray(); Arrays.sort(chars); String newStrKey = new String(chars); if(map.containsKey(newStrKey)){ map.get(newStrKey).add(str); }else{ ArrayList<String> tmp = new ArrayList<String>(); tmp.add(str); map.put(newStrKey,tmp); } } // iterator the Map to find the list, that is longger than 1 Iterator<String> iter = map.keySet().iterator(); while (iter.hasNext()) { String key = iter.next(); ArrayList<String> tmp = map.get(key); if(tmp.size()>1) al.addAll(tmp); } return al; } }
Mistakes:
1: 要注意, anagram的个数必须要大于1的。
2: 这种问题,首先就应该问明白,对于边界情况,怎么定义。
例如,这道题, 对于 两个 空字符串, 也是定义为了anagram.
Input: | ["",""] |
Output: | [] |
Expected: | ["",""] |
哎,手欠啊, 刚开始,习惯性的,加了句:|| strs[0].length() == 0 --------return al1;
3: 题意理解错误, 刚开始,以为是只能有一个anagram了。
Learned:
1:when converting a char array back to String, it seems that we can use the build-in method toString(); ------- but it seems not right.
char[] charArray = {'a', 'b', 'c'};
Solution 1:
String b = new String(a);
Solution 2:
String str = String.valueOf(charArray);
其实,所有的toArray() 方法,返回的都是一个Object. 要谨慎使用。
2: 另一种 HashMap的遍历方式:
1): Iterator<String> iter = map.keySet().iterator();
2): Iterator<Entry<String, String>> iter = map.entrySet().iterator();
3): for(T t : map.KeySet()){ // do something }
No comments:
Post a Comment