Check Permutation

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

Solution 1

One way to solve this problem is to sort both of the strings, and compare the sorted version of each string.

def solution_1(string_1, string_2):
    chars_1 = list(string_1)
    chars_2 = list(string_2)

    chars_1.sort()
    chars_2.sort()

    if(chars_1 == chars_2):
        return True
    else:
        return False

If the first string has \(a\) letters, and the second has \(b\) letters, this algorithm will take time

Solution 2

We can do better. Let’s once again use a supplemental data structure to represent each of the characters in the ASCII character set. We will then iterate through the first array, incrementing the appropriate element of the newly instantiated array. Next we iterate through the second array, decreming the elements corresponding with the characters.

def solution_2(string_1, string_2):
    char_set = [0]*128

    for x in string_1:
        i = ord(x)
        char_set[i] += 1

    for y in string_2:
        i = ord(y)
        char_set[i] -= 1

    for z in char_set:
        if z != 0:
            return False

    return True

Notice this solution has time complexity, \(O(a) + O(b)\). We iterate through both of the arrays once.