Accepted Java O(n) solution in 5 lines


  • 145
    V

    The idea is simple. It creates a size 26 int arrays as buckets for each letter in alphabet. It increments the bucket value with String s and decrement with string t. So if they are anagrams, all buckets should remain with initial value which is zero. So just checking that and return

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

  • -5
    This post is deleted!

  • 0

    Well, in fact, the assumption of lower-case letters is made by the problem statement :-)


  • 13
    S

    you can test if (alphabet[t.charAt(i) - 'a'] < 0) in the second loop, if so just return false, then you don't need the third loop.


  • 1
    V

    if then it will be wrong for the input s = "aa", t = "a"


  • 1
    Q

    I think the first two loops can be merged, so this problem can be done by one-pass.


  • 0
    V

    Yes. A good point. But it needs to check prior whether the two strings are equal since problem doesn't state that :)


  • 36
    T

    I would put an extra conditional statement in the second loop. Average time will be much better as it does not have to go through the 3rd loop every time. With this line, as soon as a discrepancy is found, it will return false and break out of the loops.

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

  • 1
    K

    its better to check, and the execution can just stop if they are not same length.


  • 0
    K

    he meant one more condition in second loop, so if any in alphabet goes to negative, it is a false.


  • 0
    M

    You can check the length, and then the condition proposed by shenhualong.
    public boolean isAnagram(String s, String t) {
    if(s.length() != t.length()) return false;
    int [] a = new int [27];
    for(Character c : s.toCharArray()) a[c - 'a']++;
    for(Character c : t.toCharArray()) {
    if(a[c -'a'] == 0) return false;
    a[c - 'a']--;
    }
    return true;
    }


  • 9
    M

    You can check the length, and then the condition proposed by shenhualong

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

  • 0
    C

    Isn't that not necessarily true though?
    i.e. if s="abba" and t="aabb"


  • 0
    T

    No, not necessarily. For example,
    s= "abba"; t= "aaabb"
    In this case, in the 2nd loop, a false will be returned as soon as it sees the 3rd a. This may seem like a small improvement but it can save a lot of time for large inputs as you don't have to check till the end.


  • 0
    C

    I meant if s="abba" and t="aabb" this solution would return false even though it should return true


  • 0
    T

    No, it won't :) After the 1st loop, alphabet[0] = 2, alphabet[1] = 2. During the 2nd loop, iteration by iteration,

    alphabet[0] = 1
    alphabet[0] = 0
    alphabet[1] = 1
    alphabet[1] = 0
    

    It won't return false in the 2nd loop, neither will it in the 3rd loop. Notice that the check is < 0 and not <= 0.


  • 0
    C

    Ohhh ok I was trying to apply this logic to my solution where I combined the first two for loops into one loop. In that case, a conditional statement like this wouldn't work. Thanks for explaining to me!


  • 0
    T

    Yes, you're right, it won't work if the two loops are merged :) I hope you consider removing the downvote, if you gave me one. :)


  • 0
    C

    My apologies! Upvoted it :)


  • 0
    S

    @michel4 Yes, this is what I mean. Should check the length first and save the third loop.

    public boolean isAnagram(String s, String t) {
            if (s == null || t == null || s.length() != t.length()) return false;
            int[] map = new int[26];
            for (int i = 0; i < s.length(); i++)
                map[s.charAt(i) - 'a']++;
            for (int i = 0; i < t.length(); i++)
                if(--map[t.charAt(i) - 'a'] < 0)
                    return false;
            return true;
        }

Log in to reply
 

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