Valid Anagram


  • 0

    Click here to see the full article post


  • 0
    D

    I think s.toCharArray() costs extra space usage.

    The returned char array is mutable and the String is not mutable. Thus it has to be an extra copy of String in char[].

    For O(1) space, we should use s.charAt()


  • 0

    Yes, you are correct. I used s.toCharArray() to make the code more concise but it does use extra space. I will update the solution shortly. Thanks.


  • 0

    I have updated the solution and complexity analysis part. Please let me know if you still see any issues, thanks!


  • 0
    P

    Can someone please help me understand why this is causing a run time error?

    class Solution {
    public:
        bool isAnagram(string s, string t) {
            if(s.length()!=t.length())
                return false;
                
            vector<int> c(26,0);
            for(int i = 0;i<s.length();i++)
            {
                c[((int)s[i] - 'a')]++;
                c[((int)t[i]- 'a')]--;
            }
            
            for(int i = 0;i<c.size();i++)
            {
               if(c[i]!=0)
                return false;
            }
            
            return true;
        }
    };
    

  • 1

    @piy9 Your code is correct and it should not cause Runtime Error. Are you sure you selected C++ from the language dropdown?


  • 0
    P

    @1337c0d3r : I submitted the code and it got accepted. But clicking the RUN CODE button causes a run time error. Screenshot : http://imgur.com/JmgU4qX


  • 1

    @piy9 You need to wrap the string in double quotes, like this:

    "anagram"
    "nagaram"

  • 0
    P

    @ 1337c0d3r : Ahh thanks


  • 0
    P
    class Solution {
    public:
        bool isAnagram(string s, string t) {
            sort(s.begin(),s.end());
            sort(t.begin(),t.end());
            return s==t;
        }
    };
    

  • 0
    X

    Does anyone help me figure out why num1 is different from num2 for ("ab", "ba")?

    public class Solution {
        public boolean isAnagram(String s, String t) {
            
            String clean1= s.replaceAll("\\P{Print}", "").trim(); 
            String clean2= t.replaceAll("\\P{Print}", "").trim(); 
            if (clean1.equals(clean2)){ return true; }
           if(clean1.length()!=clean2.length()) { return false; }
               
             int num1=0; 
             int num2=0;
            for(int i=0; i<clean1.length(); i++) {
               
                num1= num1+ clean1.substring(i, i+1).hashCode(); 
                num2= num2+ clean2.substring(i, i+1).hashCode(); 
               
                if(!clean1.contains(clean2.substring(i,i+1))||
                  !clean2.contains(clean1.substring(i,i+1))||num1!=num2
                 ) {return false;}
               
                
            }
          
            return true; 
        }
    }
    

  • 0
    N

    @xwjsarah You need to remove "num1!=num2"


  • 0
    J
    bool isAnagram(char* s, char* t) {  
        char buff[128] = {0};  
        char buff_new[128] = {0};  
          
        if(s == NULL || t == NULL)  
            return false;  
          
        if (strlen(s) != strlen(t))  
            return false;  
          
        int i = 0;  
        for(i = 0 ; i < strlen(s); i ++){  
            buff[*(s+i)] += 1;  
        }  
          
        for(i = 0; i < strlen(t); i ++){  
            buff_new[*(t+i)] += 1;  
        }  
          
        if (memcmp(buff, buff_new, 128) != 0){  
            return false;  
        }  
          
        return true;  
    } 
    

  • 0
    Z

    class Solution(object):
    def isAnagram(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    for i in map(chr, range(97, 123)):
    if s.count(i) != t.count(i):
    return False
    return True


  • 0

    public class Solution {
    public boolean isAnagram(String s, String t) {
    if(s.length() != t.length()){
    return false;
    }

        int[] hash = new int[128];
        int count = s.length();
        for(char c : s.toCharArray()){
        	hash[c - 'a']++;
        }
        for(char c : t.toCharArray()){
        	if(hash[c -'a'] > 0){
        		count--;
        	}
        	hash[c - 'a']--;        	
        }        
        if(count == 0){
        	return true;
        }
        return false;
    }
    

    }


  • 0

    What is the "- 'a'" in counter [s.charAt(i) - 'a']++; for? How does the conversion of char to int work?


  • 0
    D

    @terrychu2002-gmail.com, the " -'a' " is to calculate the correct index for the hash table. Since the table is of size 26, the range of values for the index is 0-25, inclusive, but a lowercase 'a' has an ascii value of 97, thus we have to subtract 'a' from whatever the current character is in the string to get within 0-25. Does that make sense?


  • 0
    Y

    Approach #2 do two loops. Actually, we can only do 1 loop. My code is:

    class Solution(object):
    def isAnagram(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    if len(s) != len(t):
    return False

        ch_dict = {}
        for i in xrange(len(s)):
            if ch_dict.has_key(s[i]):
                ch_dict[s[i]] += 1
            else:
                ch_dict[s[i]] = 1
            
            if ch_dict.has_key(t[i]):
                ch_dict[t[i]] -= 1
            else:
                ch_dict[t[i]] = -1
            
            ### # if the counter drops to zero, delete that key
            if ch_dict[s[i]] == 0:
                del ch_dict[s[i]]
            if ch_dict.has_key(t[i]) and ch_dict[t[i]] == 0:
                del ch_dict[t[i]]
        
        if len(ch_dict) == 0:
            return True
        else:
            return False

Log in to reply
 

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