,{"property":"og:locale","content":"en_US"}],["$","meta","13",{"property":"og:image","content":"https://k5kc.com/images/og-image.png"}],["$","meta","14",{"property":"og:image:width","content":"1200"}],["$","meta","15",{"property":"og:image:height","content":"630"}],["$","meta","16",{"property":"og:image:alt","content":"K5kC | Code & More"}],["$","meta","17",{"property":"og:type","content":"website"}],["$","meta","18",{"name":"twitter:card","content":"summary_large_image"}],["$","meta","19",{"name":"twitter:title","content":"K5kC | Code & More"}],["$","meta","20",{"name":"twitter:description","content":"Practice coding problems, learn algorithms and data structures, and improve your programming skills with K5kC."}],["$","meta","21",{"name":"twitter:image","content":"https://k5kc.com/images/og-image.png"}]],"error":null,"digest":"$undefined"} 15:{"metadata":"$d:metadata","error":null,"digest":"$undefined"} 1a:Tc50,

Problem

Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix.

For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal].

Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries.

Examples

Example 1

Solution

Method 1 - Using Trie with map of children and DFS

Trie Class

We have already seen Map-based Trie Implementation, and also seen another implementation of trie here: Implement Trie.

Take a look at Trie class.

We have already seen most of the functions in Implement Trie, and here we will cover wordsByPrefix function.

The algorithm to fetch the word list is almost similar to the one for adding a word

We can use the startsWith function to check if prefix exists in trie. If we get false, we return empty list. Another way to check is we go through prefix word in the trie, and if we encounter null node, we return empty list.
Otherwise run the DFS from prefix point, and till all the leaf nodes.

Code

[{"language":"Java","code":"class Trie {\n\tstatic class TrieNode {\n\t\tprivate boolean isLeaf;\n\t\tprivate Map<Character, TrieNode> children = new HashMap<>();\n\t}\n\n\tpublic TrieNode root;\n\n\t/** Initialize your data structure here. */\n\n\tpublic Trie() {\n\t\tthis.root = new TrieNode();\n\t}\n\n\t/** Inserts a word into the trie. */\n\n\tpublic void insert(String word) {}\n\n\t/** Returns if the word is in the trie. */\n\n\tpublic boolean search(String word) {}\n\n\tpublic boolean startsWith(String prefix) {}\n\n\tpublic List<String> wordsByPrefix(String prefix) {\n\t\tList<String> ans = new ArrayList<>();\n\t\tTrieNode curr = this.root;\n\t\t// Navigate to the end of the prefix\n\t\tfor (char c: prefix.toCharArray()) {\n\t\t\tif (!curr.children.containsKey(c)) {\n\t\t\t\t// If prefix is not present, return empty list\n\t\t\t\treturn ans;\n\t\t\t}\n\n\t\t\tcurr = curr.children.get(c);\n\t\t}\n\t\t// Recursively find all words starting with the given prefix\n\t\tdfs(curr, new StringBuilder(prefix), ans);\n\t\treturn ans;\n\t}\n\n\tprivate void dfs(TrieNode node, StringBuilder path, List<String> ans) {\n\t\tif (node.isLeaf) {\n\t\t\tans.add(path.toString());\n\t\t}\n\n\t\tfor (Map.Entry<Character, TrieNode> entry: node.children.entrySet()) {\n\t\t\t// For each child, append the char and search deeper\n\t\t\tpath.append(entry.getKey());\n\t\t\tdfs(entry.getValue(), path, ans);\n\t\t\t// Backtrack to previous state to explore other paths\n\t\t\tpath.deleteCharAt(path.length() - 1);\n\t\t}\n\t}\n\n}","lang":"java"}]

8:["$","div",null,

Related Tags