O(n) Python solution using counter arrays (beats 97% of Python submissions)


  • 0
    C

    I initially thought to sort the input strings alphabetically, but that would have resulted in O(n*log(n)) time complexity, when it's possible to solve this particular problem a bit faster.

    class Solution(object):
    def isAnagram(self, s, t):
       
        if len(s) != len(t):
            return False
        
        list_s = [0]*26
        list_t = [0]*26
        
        for ch in s:
            list_s[ord(ch)-97] += 1
        for ch in t:
            list_t[ord(ch)-97] += 1
        
        return list_s == list_t

  • 1
    M

    you don't need 2 frequency lists. One is enough and when you iterate through the second string (t), you decrement 1 for each character from the first frequency list. Then, if you have a negative value there, you return false.


  • 0
    C

    That is a good idea.


Log in to reply
 

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