[Java ] Beating 90.97% solution with int bucket doing letters count, Including thoughts on "follow-up"


  • 0

    Basically, we count number of letters for each letter in t and s, compare the counts, return true if contains exact letters and corresponding counts for each letter.

        int[] s_en = new int[26];
        int[] t_en = new int[26];
        
        for(char ch: s.toCharArray())
        {
            s_en[ch-'a']++;
        }
        for(char ch: t.toCharArray())    
        {
            t_en[ch-'a']++;
        }
        
        for(int i=0; i<26; i++){
            if(s_en[i]!=t_en[i]){
                return false;
            }
        }
        return true;
    

    Follow-up : what if characters contains unicode character?
    Solution: as we know Ascii define 128 characters by assigning characters value among ....0 - 127, and unicode define more characters by assigning value 0 - 2^31. which is pretty big number, so we can consider hashMap to do word count, and compare counts for two string.
    However, if problem is specifically constrained to some Unicode character, we can just add them in on top of the lowercase count encoding bucket int[26+m], and then do the word count and still achieve optimal running time.
    I's love to hear different voice on the follow-up, poke me if any~


  • 1
    L

    We can reduce one loop. :)

        public boolean isAnagram(String s, String t) {
            if(s.length()!=t.length()) return false;
            
            int[] alphabets = new int[26];
            for(char ch: s.toCharArray()){
                alphabets[ch-'a'] ++;
            }
            
            for(char ch: t.toCharArray()){
               alphabets[ch-'a']--;
               if(alphabets[ch-'a']<0) return false;
            }
            
            return true;
        }
    

  • 0

    @l78 Great idea!, this is definitely better. Voted up.
    More thoughts:
    Taking advantage of the letters count array of the first string, is it sort of reducing half of the total running time?

    However, both yours and mine are time of O(n), and space of O(n), but yours is still better in following ways:
    1. The longer the string, the more significantly your way is better than mine.
    2. using less space actually, ( mine: O(2n) your O(n), although they are same)


  • 0
    L

    @xuehaohu Yeah, the time complexity remains the same O(n).
    About the total running time, I think both of the methods are around 2N. Yours is 2N+26. Mine is: N<t<2N. So almost the same.


Log in to reply
 

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