Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Trie

Implement a Trie

Medium · Trie · Asked at Amazon, Google, Microsoft, Uber, Twitter

Implement a prefix tree with these operations:

Input

First line: q. Next q lines: one operation each (lowercase words).

Output

One line for every search and startsWith.

Constraints

Each node has up to 26 children and an "end of word" flag. All operations are O(length).

Example 1

Input

6
insert apple
search apple
search app
startsWith app
insert app
search app

Output

true
false
true
true

Example 2

Input

2
search a
startsWith a

Output

false
false

Hints

  1. Each node stores links to children (one per letter) and a flag "a word ends here".
  2. search needs the end flag on the last node; startsWith only needs the path to exist.

Approach

insert walks the word from the root, creating missing children, and marks the final node as a word end. walk(s) follows the letters and returns the reached node or null. search(w) = node exists and is a word end; startsWith(p) = node exists. All operations take O(length).

Complexity: O(length) per operation · O(total inserted length · 26) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct TrieNode {
    int next[26];
    bool end = false;
    TrieNode() { memset(next, -1, sizeof next); }
};
vector<TrieNode> t(1);

int walk(const string &s) {
    int cur = 0;
    for (char c : s) {
        cur = t[cur].next[c - 'a'];
        if (cur < 0) return -1;
    }
    return cur;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    string op, w;
    while (q--) {
        cin >> op >> w;
        if (op == "insert") {
            int cur = 0;
            for (char c : w) {
                if (t[cur].next[c - 'a'] < 0) {
                    t[cur].next[c - 'a'] = t.size();
                    t.emplace_back();
                }
                cur = t[cur].next[c - 'a'];
            }
            t[cur].end = true;
        } else {
            int node = walk(w);
            bool ok = op == "search" ? node >= 0 && t[node].end : node >= 0;
            cout << (ok ? "true" : "false") << "\n";
        }
    }
    return 0;
}

Python solution

import sys

data = sys.stdin.read().split()
q = int(data[0])
root, END, out = {}, "$", []


def walk(s):
    node = root
    for c in s:
        node = node.get(c)
        if node is None:
            return None
    return node


for i in range(q):
    op, w = data[1 + 2 * i], data[2 + 2 * i]
    if op == "insert":
        node = root
        for c in w:
            node = node.setdefault(c, {})
        node[END] = True
    elif op == "search":
        node = walk(w)
        out.append("true" if node is not None and END in node else "false")
    else:
        out.append("true" if walk(w) is not None else "false")
print("\n".join(out))

Java solution

import java.util.*;
import java.io.*;

public class Main {
    static class TrieNode {
        TrieNode[] next = new TrieNode[26];
        boolean end;
    }

    static TrieNode root = new TrieNode();

    static TrieNode walk(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            cur = cur.next[c - 'a'];
            if (cur == null) return null;
        }
        return cur;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int q = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String op = st.nextToken(), w = st.nextToken();
            if (op.equals("insert")) {
                TrieNode cur = root;
                for (char c : w.toCharArray()) {
                    if (cur.next[c - 'a'] == null) cur.next[c - 'a'] = new TrieNode();
                    cur = cur.next[c - 'a'];
                }
                cur.end = true;
            } else {
                TrieNode node = walk(w);
                boolean ok = op.equals("search") ? node != null && node.end : node != null;
                sb.append(ok).append('\n');
            }
        }
        System.out.print(sb);
    }
}

Solve Implement a Trie online · All practice problems