<jupyter_start><jupyter_text>This notebook was prepared by [<NAME>](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](Constraints)* [Test Cases](Test-Cases)* [Algorithm: Compare Sorted Strings](Algorithm:-Compare-Sorted-Strings)* [Code: Compare Sorted Strings](Code:-Compare-Sorted-Strings)* [Algorithm: Hashmap Lookup](Algorithm:-Hash-Map-Lookup)* [Code: Hashmap Lookup](Code:-Hash-Map-Lookup)* [Unit Test](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 StringsPermutations 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 FalseComplexity:* Time: O(n log n) from the sort, in general* Space: O(n)  Code: Compare Sorted Strings<jupyter_code>def permutations(str1, str2):
    return sorted(str1) == sorted(str2)<jupyter_output><empty_output><jupyter_text>Algorithm: Hash Map LookupWe'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 FalseNotes:* 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<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Unit Test<jupyter_code>%%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()
run -i test_permutation_solution.py<jupyter_output>Success: test_permutation
Success: test_permutation
StarcoderdataJupyterStructuredCleanDedup