3

I wrote a program to find all possible words with a list of given letters in a ternary search tree. The output is a sorted set of all words. Following is the python code for finding the words:

def _find_words(self, node: Node, letters: str, buffer=''):
    if node is None:
        return
    for c in letters:
        if node.key < c:
            self._find_words(node.high, letters, '')
        elif node.key > c:
            self._find_words(node.low, letters, '')
        else:
            buffer += node.key
            if node.isEnd:
                self.words.add(buffer)
                self._find_words(node.equal, 
                                letters.replace(node.key, '', 1), buffer)

The tree contains the following words: cat, acts, act, actor, at, bug, cats, up, actors, upper

I get the following output for the letters 'abugpscort':

['acts', 'cats', 'cat', 'act', 'bug', 'ors', 'up', 'or', 't']

whereas the output should be:

['actors', 'actor', 'acts', 'cats', 'cat', 'act', 'bug', 'up', 'at']

How can I fix this?

Pacu
  • 163
  • 1
  • 2
  • 8
  • 1
    I would suggest not modifying the `letters` variable while you iterate over it. Since you are removing characters, you are most likely skipping certain values – OneCricketeer Jan 09 '16 at 12:25
  • 1
    I find weird that in your algorithm both `key < c` and `key > c` cases do not depend of c or key. Aren't these two explorations supposed to be before and after the for loop, to add words in the buffer in the right order ? Just a thought, I'm not really sure I fully grasp how your algorithm is supposed to work. – Diane M Jan 09 '16 at 13:15
  • I have found the solution. @ArthurHavlicek You're right. The for loop and the comparisons were unnecessary. I moved the explorations outside and with a little modification of the above code, it works fine now. – Pacu Jan 09 '16 at 19:08
  • @cricket_007 I do not change the letters variable. When I put the argument as `letters.replace(node.key, '', 1)` it creates a new copy of the letters variable and replace the character in the copy. This is necessary to ensure that the number of any character in a word do not exceed the number of times it occurs in the letters variable. For e.g. if the tree contains "tools" and I input "lot", the program should return an empty set, which otherwise returns {'tool'} without the above bit of code. – Pacu Jan 09 '16 at 19:19
  • Ah, okay. Wasn't actually sure if that method made a new copy or directly modified the variable – OneCricketeer Jan 09 '16 at 19:23

0 Answers0