This notebook was prepared by Donne Martin. Source and license info is on GitHub.
find
only match exact words with a terminating character?list_words
only return words with a terminating character?root / | \ h a* m / \ \ \ a e* t* e* / \ / \ s* t* n* t* / s* find * Find on an empty trie * Find non-matching * Find matching insert * Insert on empty trie * Insert to make a leaf terminator char * Insert to extend an existing terminator char remove * Remove me * Remove mens * Remove a * Remove has list_words * List empty * List general case
Refer to the Solution Notebook. If you are stuck and need a hint, the solution notebook's algorithm discussion might be a good place to start.
from collections import OrderedDict
class Node(object):
def __init__(self, data, parent=None, terminates=False):
# TODO: Implement me
pass
class Trie(object):
def __init__(self):
# TODO: Implement me
pass
def find(self, word):
# TODO: Implement me
pass
def insert(self, word):
# TODO: Implement me
pass
def remove(self, word):
# TODO: Implement me
pass
def list_words(self):
# TODO: Implement me
pass
The following unit test is expected to fail until you solve the challenge.
# %load test_trie.py
import unittest
class TestTrie(unittest.TestCase):
def test_trie(self):
trie = Trie()
print('Test: Insert')
words = ['a', 'at', 'has', 'hat', 'he',
'me', 'men', 'mens', 'met']
for word in words:
trie.insert(word)
for word in trie.list_words():
self.assertTrue(trie.find(word) is not None)
print('Test: Remove me')
trie.remove('me')
words_removed = ['me']
words = ['a', 'at', 'has', 'hat', 'he',
'men', 'mens', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Test: Remove mens')
trie.remove('mens')
words_removed = ['me', 'mens']
words = ['a', 'at', 'has', 'hat', 'he',
'men', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Test: Remove a')
trie.remove('a')
words_removed = ['a', 'me', 'mens']
words = ['at', 'has', 'hat', 'he',
'men', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Test: Remove has')
trie.remove('has')
words_removed = ['a', 'has', 'me', 'mens']
words = ['at', 'hat', 'he',
'men', 'met']
for word in words:
self.assertTrue(trie.find(word) is not None)
for word in words_removed:
self.assertTrue(trie.find(word) is None)
print('Success: test_trie')
def test_trie_remove_invalid(self):
print('Test: Remove from empty trie')
trie = Trie()
self.assertTrue(trie.remove('foo') is None)
def main():
test = TestTrie()
test.test_trie()
test.assertRaises(KeyError, test.test_trie_remove_invalid)
if __name__ == '__main__':
main()
Review the Solution Notebook for a discussion on algorithms and code solutions.