Discover data structures and algorithms using Python. Gain insights into solving real-world problems and typical interview questions with detailed reviews, explanations, and hands-on coding exercises.

Data structures and algorithms are among the most fundamental concepts of Computer Science. Whether it’s real-world problems you’re trying to solve or the typical coding question asked in an interview, almost every problem requires you to demonstrate a deep understanding of data structures and algorithms. 

This course is a detailed review of some of the most common data structures and algorithms that you’ll see in interviews and your everyday work. With implementation details, thorough explanations, and hands-on coding exercises, you’ll quickly gain the confidence you need to solve any problem, no matter the situation.

Data Structures and Algorithms in Python

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:

# 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 sorted using the `sorted` function which returns a list. That list is again turned into a string using the `join` function.  At this point, `str_1` and `str_2` will be two strings with all the characters sorted in them. 

Now if `str_1` is a permutation of `str_2`, all the characters will be the same in the sorted version of both the strings. We'll check this using the `for` loop on **line 16** which runs from `i` equal `0` to `i` equal `n-1`. To traverse the strings, we make use of `n` which is set to `len(str_1)`.  So, on **line 17**, we check for the equality of the characters on the same index. If, in any iteration, `str_1[i]` is not equal to `str_2[i]`, `False` is returned on **line 18**. Otherwise, if `False` is never returned from the function, `True` is returned on **line 19**.

As we are using sorting to check for permutations, the time complexity for this solution is $O(n log n)$ while space complexity is $O(1)$ as there is no extra use of space. 

# Solution 2

As Solution 1 has $O(n log n)$ complexity, we need something better. Solution 2 makes use of a hash table to reach a time complexity of $O(n)$. 

## Implementation

Let's find out how by having a look at the code below:

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

Introduction

Stack

Singly Linked Lists

Circular Linked Lists

Doubly Linked Lists

Arrays

Binary Trees

Binary Search Trees

Binary Search

Recursion

String Processing

Check Permutation