def permutations(str1, str2):
    return sorted(str1) == sorted(str2)

"""
Explanation: <small><i>This notebook was prepared by Donne Martin. Source and license info is on GitHub.</i></small>
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
End of explanation
"""


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

"""
Explanation: 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
End of explanation
"""


%%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

"""
Explanation: Unit Test
End of explanation
"""


