Search⌘ K
Home
Courses
Data Structures and Algorithms in Python

Check Permutation

Explore how to identify if one string is a permutation of another using Python. Understand two approaches, including sorting and hash table techniques, and analyze their time and space complexities. This lesson equips you to implement and optimize common string permutation checks.

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:

Python 3.5
# 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 11-12, both the strings are ...