Trie — Prefix Match & Autocomplete

Prefix Matching

Walk the trie to the end of the prefix. Then DFS from that node to collect all words that branch out from there. This is exactly how autocomplete works in search bars and IDEs.

Algorithm

findPrefix(prefix):
  node = walk trie along prefix chars
  if path breaks → no matches
  else → DFS from node, collect all words
// DFS appends chars until isEnd nodes

🔍 Live Autocomplete

Pre-loaded with common words. Type a prefix to see matches in real time.

Type a prefix above to see autocomplete suggestions from the trie.

Dictionary (0 words)

C++ — Prefix Search / Autocomplete

void dfs(TrieNode* node, string& path,
         vector<string>& results) {
    if (node->isEnd)
        results.push_back(path);
    for (int i = 0; i < 26; i++) {
        if (node->children[i]) {
            path += ('a' + i);
            dfs(node->children[i], path, results);
            path.pop_back();
        }
    }
}

vector<string> autocomplete(string prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        if (!node->children[c - 'a'])
            return {}; // no matches
        node = node->children[c - 'a'];
    }
    vector<string> results;
    string path = prefix;
    dfs(node, path, results);
    return results;
}

Complexity

Prefix Walk

O(P)

P = prefix length.

Collect Results

O(K × L)

K matching words of avg length L.

📝 Notes

▼