Return the string in Trie

user_13626590 0
Viewed 136

I have this Trie:

                a
               / \
              b   c
             / \   \
            t   y   u
           2     5   3
numbers at leaf stands for frequency, stored at the terminal node

and I have default Trie search function to search for a string. When I do search('a'), it'll return aby since it is the most frequently inserted string. Frequency is stored by self.count in my function. I'd prefer not to post my code.

How would you approach solving and returning the nodes from a to y? Thank you in advance.

trie python
1 Answers

You can use a recursive generator function to traverse the trie and produce all strings that include the search value as a substring:

Simple trie setup:

class Trie:
   def __init__(self, l=None):
      self.l, self.count, self.tree = l, 0, []
   def insert_l(self, word):
      if word:
         if not (n:=[i for i in self.tree if i.l == word[0]]):
            self.tree.append(Trie(word[0]))
            self.tree[-1].add_word(word)
         else:
            n[-1].add_word(word)
   def add_word(self, word):
      if self.l is not None:
         self.count += 1
      self.insert_l(word if self.l is None else word[1:])

Now, a search method can be added to Trie:

class Trie:
    ...
    def search(self, word):
      def _search(t, c = []):
         if not t.tree:
            yield c+[t]
         else:
            for i in t.tree:
              yield from _search(i, c if t.l is None else c+[t])
      if (l:=[(j, i) for i in _search(self) if word in (j:=''.join(k.l for k in i))]):
         return max(l, key=lambda x:x[-1][-1].count)[0]

t = Trie()
words = ['abt', 'abt', 'aby', 'aby', 'aby', 'aby', 'aby', 'acu', 'acu', 'acu']
for word in words:
   t.add_word(word)

print(t.search('a'))

Output:

'aby'
user_73267380
Related