Java solution. Use HashMap, use simple string uid as key.


  • 5
    S

    We count the number of appearance of each char in a word, and generate a uid string like "num[0]/num[1]/..../num[25]/", and use it as the key of this word. We then use hash table to put the words that have the same uid together.

    public class Solution {
    public List<String> anagrams(String[] strs) {
        List<String> res = new LinkedList<String>();
        if (strs.length==0 || strs.length==1) return res;
        
        Map<String,List<String>> resMap = new HashMap<String,List<String>>();
        List<String> uidList = new ArrayList<String>(); 
    
        for (int i=0;i<strs.length;i++){
            String uid = getUID(strs[i]);
            if (resMap.containsKey(uid))
                resMap.get(uid).add(strs[i]);
            else {
                List<String> list = new LinkedList<String>();
                list.add(strs[i]);
                resMap.put(uid,list);
                uidList.add(uid);
            }
        }
    
        for (int i=0;i<uidList.size();i++){
            List<String> list = resMap.get(uidList.get(i));
            if (list.size()>1) res.addAll(list);
        }
    
        return res;
    }
    
    
    public String getUID(String s){
        int[] num = new int[26];
        Arrays.fill(num,0);
        for (int i=0;i<s.length();i++){
            char temp = s.charAt(i);
            int val = temp-'a';
            num[val]++;
        }
    
        String uid = "";
        for (int i=0;i<26;i++)
            uid+=Integer.toString(num[i])+"/";
    
        return uid;
    
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.