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.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class Trie {
	static class TrieNode {
		private boolean isLeaf;
		private Map<Character, TrieNode> children = new HashMap<>();
	}

	public TrieNode root;

	/** Initialize your data structure here. */

	public Trie() {
		this.root = new TrieNode();
	}

	/** Inserts a word into the trie. */

	public void insert(String word) {}

	/** Returns if the word is in the trie. */

	public boolean search(String word) {}

	public boolean startsWith(String prefix) {}

	public List<String> wordsByPrefix(String prefix) {
		List<String> ans = new ArrayList<>();
		TrieNode curr = this.root;
		// Navigate to the end of the prefix
		for (char c: prefix.toCharArray()) {
			if (!curr.children.containsKey(c)) {
				// If prefix is not present, return empty list
				return ans;
			}

			curr = curr.children.get(c);
		}
		// Recursively find all words starting with the given prefix
		dfs(curr, new StringBuilder(prefix), ans);
		return ans;
	}

	private void dfs(TrieNode node, StringBuilder path, List<String> ans) {
		if (node.isLeaf) {
			ans.add(path.toString());
		}

		for (Map.Entry<Character, TrieNode> entry: node.children.entrySet()) {
			// For each child, append the char and search deeper
			path.append(entry.getKey());
			dfs(entry.getValue(), path, ans);
			// Backtrack to previous state to explore other paths
			path.deleteCharAt(path.length() - 1);
		}
	}

}