Delete Word from Trie

Problem

Simulate a trie that supports insert, search, and delete.

operations contains "insert", "search", or "delete"; words provides the argument. insert records None, search records whether the exact word is currently present, and delete removes the word once and records whether it was found. Deleting a word must not remove longer words that share its prefix, and empty branches should be pruned.

Return the list of recorded results.

Hint

Track two things while unwinding: whether the word was found, and whether the node can be pruned.

Test cases

case 1

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

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

case 2

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

expected: [null,false,true]

case 3

in: [["delete"],["x"]]

expected: [false]

case 4

in: [["insert","delete","delete"],["abc","abc","abc"]]

expected: [null,true,false]

Starter codePython

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

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