This notebook was prepared by Donne Martin. Source and license info is on GitHub.
Permutations contain the same strings but in different orders. This approach could be slow for large strings due to sorting.
Complexity:
class Permutations(object):
def is_permutation(self, str1, str2):
if str1 is None or str2 is None:
return False
return sorted(str1) == sorted(str2)
We'll keep a hash map (dict) to keep track of characters we encounter.
Steps:
Notes:
Complexity:
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
%%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
run -i test_permutation_solution.py
Success: test_permutation Success: test_permutation