Thursday, November 6, 2014

Facebook: Find all the anagrams in an array of strings

Find all the anagrams in an array of strings
Leetcode: Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
A wrong answer:
public class Solution {
    public List<String> anagrams(String[] str) {
        List<String> result = new ArrayList<String>();
        
        if (str == null || str.length <= 1) {
            return result;
        }
        
        Map<String, List<String> map = new HashMap<String, List<String>>();
        
        for (int i = 0; i < str.length; i++) {
            char[] temp = str[i].toCharArray();
            Arrays.sort(temp);
            String curr = temp.toString();
            
            if (!map.containsKey(curr)) {
                List<String> list = new ArrayList<String>();
                list.add(str[i]);
                map.put(curr, list);
            } else {
                List<String> tempList = map.get(curr);
                tempList.add(str[i]);
                map.put(curr, tempList);
            }
        }
        
        // Dump the hash map to result lsit
        for (List<String> list : map.values()) {
            if (list.size() > 1) {
                result.addAll(list);
            }
        }
        
        return result;
    }
}

Submission Result: Wrong Answer

Input:
["",""]
Output:
[]
Expected:
["",""]











Why this answer is wrong:? 

That is simply because of using the temp.toString() method, which is wrong.
Usually there are two methods to convert a char array to string:
1. Use string constructor: String newString = new String(charArr);
2. Use String newString = String.valueOf(charArr);

So the correct solution is:

public class Solution {
    public List<String> anagrams(String[] str) {
        List<String> result = new ArrayList<String>();
        
        if (str == null || str.length <= 1) {
            return result;
        }
        
        Map<String, List<String> map = new HashMap<String, List<String>>();
        
        for (int i = 0; i < str.length; i++) {
            char[] temp = str[i].toCharArray();
            Arrays.sort(temp);
            String curr = new String[temp];
            
            if (!map.containsKey(curr)) {
                List<String> list = new ArrayList<String>();
                list.add(str[i]);
                map.put(curr, list);
            } else {
                List<String> tempList = map.get(curr);
                tempList.add(str[i]);
                map.put(curr, tempList);
            }
        }
        
        // Dump the hash map to result lsit
        for (List<String> list : map.values()) {
            if (list.size() > 1) {
                result.addAll(list);
            }
        }
        
        return result;
    }
}

No comments:

Post a Comment