question check permutation given two strings write a method to decide if one is a permutation of the other source cracking the code interview 6th edition question 1 2 time complexity every letter must be looped which means on time complexity then we must check if each letter is in the dictionary which is another on time complexity overall the total time complexity is on2 case 1 not matching length case 2 both strings have a length of zero case 3 one letter strings case 4 length greater than 1 for both strings and lengths are equal loop through each letter looping is an on operation check if it the letter is in the dictionary checking is on operation loop through each letter looping is an on operation check if it the letter is in the dictionary checking is on operation additional solution by sorting the letters of the words case 1 not matching length case 2 both strings have a length of zero case 3 one letter strings case 4 length greater than 1 for both strings and lengths are equal loop through each letter looping is an o n operation check if it the letter is in the dictionary checking is o n operation loop through each letter looping is an o n operation check if it the letter is in the dictionary checking is o n operation additional solution by sorting the letters of the words
letter_counts = {}


def check_permutations(word1, word2):
    
    if len(word1) != len(word2):
        return False
    
    if len(word1) == 0 and len(word2) == 0:
        return True
    
    if len(word1) == 1 and len(word2) == 1:
        return word1[0] == word2[0]
    
    else:
        populate_letter_count(word1)
        
        for letter in word2:
            
            if letter_counts.get(letter) is not None:
                curr_count = letter_counts.get(letter)
                if curr_count == 1:
                    letter_counts.pop(letter)
                else:
                    letter_counts[letter] = curr_count - 1
            else:
                return False
        return True


def populate_letter_count(word1):
    
    for letter in word1:
        
        if letter_counts.get(letter) is None:
            letter_counts[letter] = 1
        else:
            curr_count = letter_counts.get(letter) + 1
            letter_counts[letter] = curr_count



def check_permutation2(word1, word2):
    sorted(word1) == sorted(word2)