11. DP, Greedy & Tries

Tries (prefix trees)

0 of 5 activities0%

Reading 1

Character by character

Open

A trie node has up to Σ children (e.g., 26 letters) and a flag isEnd.

Insert/search walk character links. Great for autocomplete and word dictionaries.

Space can be large; compressed tries exist.

struct TrieNode {
  TrieNode* next[26];
  bool end;
};

Check 2

Open

Tries excel at

Fill in 3

Open

Try it 4

Open

Does "app" share prefix with "apple"?

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read word and prefix. Print yes if word starts with prefix, else no.

main.cpp

Loading editor…