This notebook was prepared by Donne Martin. Source and license info is on GitHub.

# Solution Notebook¶

## Constraints¶

• Can we assume the string is ASCII?
• Yes
• Note: Unicode strings could require special handling depending on your language
• Is whitespace important?
• Yes
• Is this case sensitive? 'Nib', 'bin' is not a match?
• Yes
• Can we use additional data structures?
• Yes
• Can we assume this fits in memory?
• Yes

## Test Cases¶

• One or more None inputs -> False
• One or more empty strings -> False
• 'Nib', 'bin' -> False
• 'act', 'cat' -> True
• 'a ct', 'ca t' -> True
• 'dog', 'doggo' -> False

## Algorithm: Compare Sorted Strings¶

Permutations contain the same strings but in different orders. This approach could be slow for large strings due to sorting.

• Sort both strings
• If both sorted strings are equal
• return True
• Else
• return False

Complexity:

• Time: O(n log n) from the sort, in general
• Space: O(n)

## Code: Compare Sorted Strings¶

In [1]:
class Permutations(object):

def is_permutation(self, str1, str2):
if str1 is None or str2 is None:
return False
return sorted(str1) == sorted(str2)


## Algorithm: Hash Map Lookup¶

We'll keep a hash map (dict) to keep track of characters we encounter.

Steps:

• Scan each character
• For each character in each string:
• If the character does not exist in a hash map, add the character to a hash map
• Else, increment the character's count
• If the hash maps for each string are equal
• Return True
• Else
• Return False

Notes:

• Since the characters are in ASCII, we could potentially use an array of size 128 (or 256 for extended ASCII), where each array index is equivalent to an ASCII value
• Instead of using two hash maps, you could use one hash map and increment character values based on the first string and decrement based on the second string
• You can short circuit if the lengths of each string are not equal, although len() in Python is generally O(1) unlike other languages like C where getting the length of a string is O(n)

Complexity:

• Time: O(n)
• Space: O(n)

## Code: Hash Map Lookup¶

In [2]:
from collections import defaultdict

class PermutationsAlt(object):

def is_permutation(self, str1, str2):
if str1 is None or str2 is None:
return False
if len(str1) != len(str2):
return False
unique_counts1 = defaultdict(int)
unique_counts2 = defaultdict(int)
for char in str1:
unique_counts1[char] += 1
for char in str2:
unique_counts2[char] += 1
return unique_counts1 == unique_counts2


## Unit Test¶

In [3]:
%%writefile test_permutation_solution.py
import unittest

class TestPermutation(unittest.TestCase):

def test_permutation(self, func):
self.assertEqual(func(None, 'foo'), False)
self.assertEqual(func('', 'foo'), False)
self.assertEqual(func('Nib', 'bin'), False)
self.assertEqual(func('act', 'cat'), True)
self.assertEqual(func('a ct', 'ca t'), True)
self.assertEqual(func('dog', 'doggo'), False)
print('Success: test_permutation')

def main():
test = TestPermutation()
permutations = Permutations()
test.test_permutation(permutations.is_permutation)
try:
permutations_alt = PermutationsAlt()
test.test_permutation(permutations_alt.is_permutation)
except NameError:
# Alternate solutions are only defined
# in the solutions file
pass

if __name__ == '__main__':
main()

Overwriting test_permutation_solution.py

In [4]:
run -i test_permutation_solution.py

Success: test_permutation
Success: test_permutation