CODEWITHSUNDEEP
pythonsearchtrie
Albin Antony
Albin Antony

Reputation: 805

Prefix search in a Trie dictionary

I have a sample dictionary 

    {  
   'A':{  
      'P':{  
         'P':{  
            'L':{  
               'I':{  
                  'E':{  
                     'S':{  
                        '*':True
                     }
                  }
               },
               'E':{  
                  'S':{  
                     '*':True
                  },
                  '*':True
               }
            }
         },
         'E':{  
            '*':True
         }
      }
   }
}

Here {*:True} denotes end of the word. I need to find all the possible words I can generate from the dictionary starting with a prefix. For example, the words that I can generate from the above dictionary with the various prefixes are below.

  1. 'AP' - > "APPLE", "APPLES" "APE", "APPLIES"

  2. 'APP' -> "APPLE", "APPLES", "APPLIES"

  3. 'APPLE' -> "APPLE", "APPLES"

I'm basically trying to implement a Trie data structure using a dictionary and perform a prefix search. I think I should implement some recursive algorithm to find all the possible outcomes. I am not able to figure out how to implement it.

Upvotes: 3

Views: 850

Answers (2)

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion with a generator:

data = {'A': {'P': {'P': {'L': {'I': {'E': {'S': {'*': True}}}, 'E': {'S': {'*': True}, '*': True}}}, 'E': {'*': True}}}}
def combos(d, c = []):
  for a, b in d.items():
    yield from [''.join(c)] if isinstance(b, bool) else combos(b, c+[a])


print(list(combos(data['A']['P'], ['A', 'P'])))

Output:

['APPLIES', 'APPLES', 'APPLE', 'APE']

Upvotes: 2

hiro protagonist
hiro protagonist

Reputation: 46849

i got curious and came up with this recursive variant:

tree = {
    "A": {
        "P": {
            "P": {
                "L": {
                    "I": {"E": {"S": {"*": True}}},
                    "E": {"S": {"*": True}, "*": True},
                }
            },
            "E": {"*": True},
        }
    }
}


def descend(node, prefix=""):
    if prefix and prefix[-1] == "*":
        print(prefix[:-1])
        return
    for letter, node in node.items():
        descend(node, prefix + letter)


descend(tree)

it prints:

APPLIES
APPLES
APPLE
APE

Upvotes: 2

Related Questions