Trie Insert, Search, and StartsWith

Problem

Simulate a trie (prefix tree) supporting insert, search, and starts_with.

operations contains "insert", "search", or "starts_with"; words provides the argument. insert records None, search records whether the exact word was inserted, and starts_with records whether any inserted word begins with the given prefix.

Return the list of recorded results.

Hint

Store an end-of-word marker on the node where a full word finishes.

Test cases

case 1

in: [["insert","search","search","starts_with"],["apple","apple","app","app"]]

expected: [null,true,false,true]

case 2

in: [["insert","insert","search","starts_with","starts_with"],["app","apple","apple","appl","b"]]

expected: [null,null,true,true,false]

case 3

in: [["search"],["a"]]

expected: [false]

case 4

in: [["insert","search"],["a","a"]]

expected: [null,true]

Starter codePython

def trie_ops(operations, words):
    # Your code here
    pass

4 test cases · run your code against them in the editor