0

I am setting up a trie, here is my code:

class Trie:
    def __init__(self):
        self.root = {}
        self.endSymbol = "*"

    def add(self, word):
        node = self.root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node[self.endSymbol] = word

def multiStringSearch(smallStrings):
    trie = Trie()

    for word in smallStrings:
        trie.add(word)

    return trie

print(multiStringSearch(["abc", "mnopqr", "wyz", "no", "e", "tuuv","abb"])

Two questions:

  1. How can I print out the trie?
  2. For some reason, the above doesn't produce the correct trie, for example, "mnopqr" and "no" should be under the same root for the 'n', but they appear separately by the above construction.

Thanks John and Ervin for your contributions, can I just check then, which of the following would the trie set-up produce?:

enter image description here

Patrick_Chong
  • 434
  • 2
  • 12

2 Answers2

4
  1. For printing out the trie:
class Trie:
    def __init__(self):
        self.root = {}
        self.endSymbol = "*"

    def add(self, word):
        node = self.root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node[self.endSymbol] = word

    def __str__(self):
        return str(self.root)


def multiStringSearch(smallStrings):
    trie = Trie()

    for word in smallStrings:
        trie.add(word)

    return trie


if __name__ == "__main__":
    trie = multiStringSearch(["abc", "mnopqr", "wyz", "no", "e", "tuuv","abb"])
    print(trie)
  1. No, they should not be under the same root, because they do not share a common prefix. In your example abb and abc should be under the same root, and they are if you print out the `trie.
Ervin Szilagyi
  • 14,274
  • 2
  • 25
  • 40
  • Thanks Ervin, could you also kindly briefly explain when to use the if __name__ == " __main__"? I read the following article but still couldn't understand when to use it: https://www.freecodecamp.org/news/if-name-main-python-example/ – Patrick_Chong Jan 06 '22 at 10:09
  • You may want to check this out: https://www.youtube.com/watch?v=FRxDmVVm0d0&ab_channel=anthonywritescode or this answer: https://stackoverflow.com/a/60017299/7661119 In short, it is not something necessary to have in smaller scripts. I personally use it, because Pycharm IDE recognizes it as an entrypoint for my script. – Ervin Szilagyi Jan 06 '22 at 16:31
  • Basically, the code bellow the scope `if __name__ == "__main__"` is executed only if I invoke my script from the terminal or from an IDE. This can help me to have a `main` function (entrypoint if you coded in C/C++) for my script, but I also can be import the functions from my script in other scripts, for example when I want to unit test something. – Ervin Szilagyi Jan 06 '22 at 16:47
0

ad 1) The following code will print the tree with indentation (for easier examination of the tree)

class Trie:
    def __init__(self):
        self.root = {}
        self.endSymbol = "*"

    def add(self, word):
        node = self.root
        for letter in word:
            if letter not in node:
                node[letter] = {}
            node = node[letter]
        node[self.endSymbol] = word

    def __str__(self):
        return self.__format(self.root)

    def __format(self, node, indent = 0):
        s = ''

        for key in node:
            s += ' ' * indent
            s += key
            if key == self.endSymbol:
                s += ' => ' + node[key]
                s += '\n'
            else:
                s += '\n'
                s += self.__format(node[key], indent + 1)

        return s

def multiStringSearch(smallStrings):
    trie = Trie()

    for word in smallStrings:
        trie.add(word)

    return trie

print(multiStringSearch(["abc", "mnopqr", "wyz", "no", "e", "tuuv","abb"]))

Output:

a
 b
  c
   * => abc
  b
   * => abb
m
 n
  o
   p
    q
     r
      * => mnopqr
w
 y
  z
   * => wyz
n
 o
  * => no
e
 * => e
t
 u
  u
   v
    * => tuuv
Gerald Mayr
  • 644
  • 2
  • 13