Anagram
  • One string is an anagram of another if the second is simply a rearrangement of the first
  • For example, 'heart' and 'earth' are anagrams, 'python' and 'typhon' are anagrams
  • def anagram(s1,s2):
        """Check if s1 is a anagram of s2
        
        Args:
            s1 (str), a string consisted of 26 letters
            s2 (str), a string consisted of 26 letters
            
        Return:
            boolean
        """
        if len(s1) != len(s2): # O(1)
            return False
        
        s1 = s1.lower() # O(n)
        s2 = s2.lower() # O(n)
        
        array_1 = [0]*26 # O(n), save 26 letters in s1
        array_2 = [0]*26 # O(n), save 26 letters in s2
        
        for letter in s1: # O(n)
            index = ord(letter) - ord('a')
            array_1[index] += 1
            
        for letter in s2: # O(n)
            index = ord(letter) - ord('a')
            array_2[index] += 1
            
        for i in range(26): # O(1)
            if array_1[i] != array_2[i]:
                return False
            
        return True
                
    s1 = 'heart'
    s2 = 'earth'
    anagram(s1, s2) # True
    
    s1 = 'python'
    s2 = 'typhon'
    anagram(s1, s2) # True
                
    Reference
  • Problem Solving with Algorithms and Data Structures using Python