Tuesday, February 26, 2013

[LeetCode] Anagrams

Thought:
Use a HashMap to store the sorted-original pairs, if there are several original string that relates to the same sorted string, they are anagrams!

Code:
import java.util.Iterator;
public class Solution {
    public ArrayList<String> anagrams(String[] strs) {
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        ArrayList<String> result = new ArrayList<String>();
       
        for (int i = 0; i < strs.length; i++) {
            String key = sortWord(strs[i]);
            if (!map.containsKey(key)) {
                ArrayList<String> value = new ArrayList<String>();
                value.add(strs[i]);
                map.put(key, value);
            }
            else {
                ArrayList<String> value = map.get(key);
                value.add(strs[i]);
                map.put(key, value);
            }
        }
        
        Iterator<ArrayList<String>> it = map.values().iterator();
        while (it.hasNext()) {
            ArrayList<String> v = it.next();
            if (v.size() >= 2) {
                result.addAll(v);
            }
        }
        
        return result;
    }
    
    public String sortWord(String word){
        char[] charArr = word.toCharArray();
        Arrays.sort(charArr);
        return new String(charArr);
    }
}

No comments:

Post a Comment