Java O(n) solution for strings of arbitrary characters


  • 13
    A

    The idea is to count how much of each character strings contain. If two strings are anagrams, they should contain the equal number of particular characters. Size of array is chosen according to the size of ASCII table.

       public class Solution {
            public boolean isAnagram(String s, String t) {
                if (s.length()!=t.length()) return false;
                int[] c=new int[256];
                for (int i=0; i<s.length(); ++i){
                    c[s.charAt(i)]++; 
                    c[t.charAt(i)]--;
                }
                
                for (int i=0; i<256; ++i){
                    if (c[i]!=0) return false;
                }
                return true;
            }
        }

  • 0

    Great extension to all ASCII codes :-)


  • 2
    E

    What about Unicode? The question has a follow up:

    Follow up: What if the inputs contain unicode characters? How would
    you adapt your solution to such case?

    The first idea strikes me is HashMap, because the size of possible character is large.
    I'm not sure if what I think is right.
    Later Update:
    I use hashmap to implement a VERY SLOW AC solution, it's not really concise and needs to be refined, but I think it may take care of all kinds of Unicode chars......


Log in to reply
 

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