This notebook was prepared by Donne Martin. Source and license info is on GitHub.
A set is an unordered collection of unique elements.
Complexity:
class UniqueCharsSet(object):
def has_unique_chars(self, string):
if string is None:
return False
return len(set(string)) == len(string)
We'll keep a hash map (set) to keep track of unique characters we encounter.
Steps:
Notes:
Complexity:
class UniqueChars(object):
def has_unique_chars(self, string):
if string is None:
return False
chars_set = set()
for char in string:
if char in chars_set:
return False
else:
chars_set.add(char)
return True
Assume we cannot use additional data structures, which will eliminate the fast lookup O(1) time provided by our hash map.
Algorithm Complexity:
class UniqueCharsInPlace(object):
def has_unique_chars(self, string):
if string is None:
return False
for char in string:
if string.count(char) > 1:
return False
return True
%%writefile test_unique_chars.py
import unittest
class TestUniqueChars(unittest.TestCase):
def test_unique_chars(self, func):
self.assertEqual(func(None), False)
self.assertEqual(func(''), True)
self.assertEqual(func('foo'), False)
self.assertEqual(func('bar'), True)
print('Success: test_unique_chars')
def main():
test = TestUniqueChars()
unique_chars = UniqueChars()
test.test_unique_chars(unique_chars.has_unique_chars)
try:
unique_chars_set = UniqueCharsSet()
test.test_unique_chars(unique_chars_set.has_unique_chars)
unique_chars_in_place = UniqueCharsInPlace()
test.test_unique_chars(unique_chars_in_place.has_unique_chars)
except NameError:
# Alternate solutions are only defined
# in the solutions file
pass
if __name__ == '__main__':
main()
Overwriting test_unique_chars.py
%run -i test_unique_chars.py
Success: test_unique_chars Success: test_unique_chars Success: test_unique_chars