Trie Collect Words with Prefix

Problem

Collect all words from the given list that start with prefix, using a trie.

Insert every word into a trie, walk down the characters of the prefix, then gather every word stored in the subtree with a depth-first search.

Return the matching words sorted in ascending lexicographic order.

Hint

The prefix walk ends at a subtree root; DFS that subtree collecting end markers.

case 1

in: [["apple","app","apricot","banana"],"ap"]

expected: ["app","apple","apricot"]

case 2

in: [["dog","deer"],"do"]

expected: ["dog"]

case 3

in: [["a"],"b"]

expected: []

case 4

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

expected: ["","a"]

case 5

in: [["tea","ted","ten"],"te"]

expected: ["tea","ted","ten"]

Starter codePython

def words_with_prefix(words, prefix):
    # Your code here
    pass

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