Data Structures and Algorithms in Python/

...

/

Check Permutation

Check Permutation

In this lesson, you will learn how to check if a string is a permutation of another string in Python.

We'll cover the following...

In this lesson, we will consider how to determine if a given string is a permutation of another string.

Specifically, we want to solve the following problem:

Given two strings, write a function to determine if one is a permutation of the other.

Here is an example of strings that are permutations of each other:

is_permutation_1 = "google"
is_permutation_2 = "ooggle"

The strings below are not permutations of each other.

not_permutation_1 = "not"
not_permutation_2 = "top"

We will solve this problem in Python and analyze the time and space complexity of our approach.

Let’s begin!

Solution 1

Implementation

A permutation of a string will have the same number of each type of character as that string as it is just a rearrangement of the letters.

Let’s have a look at the code below where we make use of this property:

Press + to interact
# Approach 1: Sorting
# Time Complexity: O(n log n)
# Space Complexity: O(1)
def is_perm_1(str_1, str_2):
    str_1 = str_1.lower()
    str_2 = str_2.lower()
    if len(str_1) != len(str_2):
        return False
    str_1 = ''.join(sorted(str_1))
    str_2 = ''.join(sorted(str_2))
    n = len(str_1)
    for i in range(n):
        if str_1[i] != str_2[i]:
            return False
    return True

Explanation

First of all, both the strings str_1 and str_2 are normalized on lines 5-6 as all the characters are converted to lowercase. On line 8, we check for a basic permutation property, i.e., the two strings that are permutations of each other have to be of the same length. Therefore, False is returned on line 9 if the length of str_1 does not equal length of str_2.

On lines ...