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

Classical interview question explained

Photo by Glen Carrie on unsplash

First let’s agree on if the strings doesn’t have the same size, fhey are different.

Solution 1

We will use sorted from Python library. If the difference was just permutation(s): sorting them should make them equal.

def permutation1(str1, str2):
    if len(str1) != len(str2):
        return False
    return "".join(sorted(str1)) == "".join(sorted(str2))

sorted: Python uses timsort function which runs in O(n) in best case and O(n log n) in average/worst case.

join: string are immutable in Python, the entire strings need to be copied. The complexity O(n) where n is the size of the output string

Solution 2

We are assuming the string is coded in ASCII (since it is ASCII the alphabet has 128 characters). We are counting each character and saving the result in a buffer and comparing the result with the second string

def permutation2(str1, str2):
    if len(str1) != len(str2):
        return False
    buffer = [0] * 128
    for c in str1:
        offset = ord(c)
        buffer[offset] += 1
    for c in str2:
        offset = ord(c)
        buffer[offset] -= 1
    for i in buffer:
        if i != 0:
            return False
    return True

Performance complexity is O(n)

Solution 3

Here is another interesting way to answer the question

from collections import Counter
def permutation3(str1, str2):
  counter = Counter()
  for letter in str1:
    counter[letter] += 1
  for letter in str2:
    if not letter in counter:
      return False
    counter[letter] -= 1
    if counter[letter] == 0:
      del counter[letter]
  return len(counter) == 0

Solution 4

def permutation4(str1, str2):
    return Counter(str1) == Counter(str2)

Benchmark

Here is the time comparison:

Any better implementation ?