Medium

Implement Trie (Prefix Tree)

085

Simulate a trie. Operations are insert, search, and startsWith. Return booleans for search and startsWith.

EXAMPLES

Example 1

Input
{
  "operations": [
    "insert",
    "search",
    "search",
    "startsWith",
    "insert",
    "search"
  ],
  "words": [
    "apple",
    "apple",
    "app",
    "app",
    "app",
    "app"
  ]
}

Output
[
  true,
  false,
  true,
  true
]

FUNCTION SHAPE

operations: stringArraywords: stringArray→boolArray

SOLUTION NOTE

It's the same template above, just with a startsWith function. Its the same traversal logic as search, except at the end we just return True instead of node.is_word, since we don't care if its a word or not. We just care that this prefix exists in the trie, meaning some word that was inserted has this prefix.

Reveal reference solution +

pythonREFERENCE

def startsWith(self, prefix: str) -> bool:
    node = self
    for c in prefix:
        if c not in node.children: return False
        node = node.children[c]
    return True

TimeO(len(word))

SpaceO(total characters)

Open on LeetCode ↗