Monday, October 21, 2013

Anagrams

Q:
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