Home

Cracking the Code Interview Series: Check Permutation

Japanese lamps Photo by Andreas Dress

Check Permutation: Given two strings, write a method to decide if one is a permutation of the other.

Examples

"abc" "bca" => True
"abc" "bca" => True
"abc" "aab" => False
"abc" "baca" => False

Questions

Solutions

Sorting & Comparing

def permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    return sorted(str1) == sorted(str2)

We can compare the two strings after sorting the characters. If the sorted strings are equal, we return True, otherwise False.

Using the Set data structure

def permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    first_set = set()
    second_set = set()

    for char in str1:
        first_set.add(char)

    for char in str2:
        second_set.add(char)

    return first_set == second_set

We always need to verify the length of the string first. Then create two sets, one for the first string, and the other for the second one.

Comparing the two sets, we know if they are equal or not, or in other terms, if it is a permutation or not.

Using a HashMap data structure

def permutation(str1, str2):
    if len(str1) != len(str2):
        return False

    characters = {}

    for char in str1:
        if char in characters:
            characters[char] += 1
        else:
            characters[char] = 1

    for char in str2:
        if char not in characters or characters[char] == 0:
            return False

        characters[char] -= 1

    return True

Using a hash map, we can map the characters from the first string to the count of this character in the string.

Iterating through the second string, we need to make sure that the character is in the hash map and the count is greater than zero. If it has, we just decrease the count for the character and move on. If it doesn't have, we can return False because it is not a permutation.

Patreon Become a Patron Coffee icon Buy me a coffee