Java Solution Use Two Run. O(m*n) runtime


  • 0
    S

    Run time is O(m*n)

    m is the maximum length of a string in strs
    n is the total number of string in strs

    I define a 26 length buffer for each word(I am using a 26 length String, each char in string represents how many times a char appear in that string). Then two anagram words will have the same string. Use it for anagram match, and it's O(1).

    First run: note down the number of appearance for each char-set.

    Second run: if a word matches a char-set, add it to output.

    public class Solution {
        static int charNum = 26;
        public ArrayList<String> anagrams(String[] strs) {
            ArrayList<String> output = new ArrayList<String>();
            HashSet<String> set = new HashSet<String>();
            HashMap<String,Integer> map = new HashMap<String, Integer>();
            for(int i = 0;i < strs.length;i++){
                // generate char set for current string
                String charSet = "";
                for(int j = 0;j < charNum;j++){charSet += 0x00;}
                for(int j = 0;j < strs[i].length();j++)
                    for(char c = 'a';c <= 'z';c++)
                        if(strs[i].charAt(j)==c){
                            char ch = (char)((int)charSet.charAt((int)(c-'a'))+1);
                            charSet = changeCharInPosition((int)(c-'a'),ch,charSet);
                        }
                
                // check existence
                if(map.get(charSet)!=null){
                    set.add(charSet);
                }
                if(map.get(charSet)==null){
                    map.put(charSet,1);
                }else{
                    int value = map.get(charSet);
                    map.put(charSet,value+1);
                }
            }
            for(int i = 0;i < strs.length;i++){
                // generate char set for current string
                String charSet = "";
                for(int j = 0;j < charNum;j++){charSet += 0x00;}
                for(int j = 0;j < strs[i].length();j++)
                    for(char c = 'a';c <= 'z';c++)
                        if(strs[i].charAt(j)==c){
                            char ch = (char)((int)charSet.charAt((int)(c-'a'))+1);
                            charSet = changeCharInPosition((int)(c-'a'),ch,charSet);
                        }
                
                // check existence
                if(set.contains(charSet)){
                    output.add(strs[i]);
                }
            }
            return output;
        }
        
        public String changeCharInPosition(int position, char ch, String str){
            String output = str.substring(0,position)+ch+str.substring(position+1,str.length());
            return output;
        }
    }

Log in to reply
 

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