Trie Backtracking in Recursion
- by Darksky
I am building a tree for a spell checker with suggestions. Each node contains a key (a letter) and a value (array of letters down that path).
So assume the following sub-trie in my big trie:
W
/ \
a e
| |
k k
| |
is word--> e e
|
...
This is just a subpath of a sub-trie. W is a node and a and e are two nodes in its value array etc...
At each node, I check if the next letter in the word is a value of the node. I am trying to support mistyped vowels for now. So 'weke' will yield 'wake' as a suggestion. Here's my searchWord function in my trie:
def searchWord(self, word, path=""):
if len(word) > 0:
key = word[0]
word = word[1:]
if self.values.has_key(key):
path = path + key
nextNode = self.values[key]
return nextNode.searchWord(word, path)
else:
# check here if key is a vowel. If it is, check for other vowel substitutes
else:
if self.isWord:
return path # this is the word found
else:
return None
Given 'weke', at the end when word is of length zero and path is 'weke', my code will hit the second big else block. weke is not marked as a word and so it will return with None. This will return out of searchWord with None.
To avoid this, at each stack unwind or recursion backtrack, I need to check if a letter is a vowel and if it is, do the checking again.
I changed the if self.values.has_key(key) loop to the following:
if self.values.has_key(key):
path = path + key
nextNode = self.values[key]
ret = nextNode.searchWord(word, path)
if ret == None:
# check if key == vowel and replace path
# return nextNode.searchWord(...
return ret
What am I doing wrong here? What can I do when backtracking to achieve what I'm trying to do?
