This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges).

Solution Notebook

Problem: Determine if a string is a permutation of another string

Constraints
Test Cases
Algorithm: Compare Sorted Strings
Code: Compare Sorted Strings
Algorithm: Hashmap Lookup
Code: Hashmap Lookup
Unit Test

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

Test Cases

One or more empty strings -> False
'Nib', 'bin' -> False
'act', 'cat' -> True
'a ct', 'ca t' -> True

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]:

    
def permutations(str1, str2):
    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


def unique_counts(string):
    dict_chars = defaultdict(int)
    for char in string:
        dict_chars[char] += 1
    return dict_chars


def permutations_alt(str1, str2):
    if len(str1) != len(str2):
        return False
    unique_counts1 = unique_counts(str1)
    unique_counts2 = unique_counts(str2)
    return unique_counts1 == unique_counts2

Unit Test



In [3]:

    
%%writefile test_permutation_solution.py
from nose.tools import assert_equal


class TestPermutation(object):

    def test_permutation(self, func):
        assert_equal(func('', 'foo'), False)
        assert_equal(func('Nib', 'bin'), False)
        assert_equal(func('act', 'cat'), True)
        assert_equal(func('a ct', 'ca t'), True)
        print('Success: test_permutation')


def main():
    test = TestPermutation()
    test.test_permutation(permutations)
    try:
        test.test_permutation(permutations_alt)
    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