DSA Sheet - Day 24 Tries

🌲 DSA Sheet – Day 24: Tries (Prefix Tree)

Tries are powerful for string-based problems involving prefixes, autocomplete, and fast dictionary lookups. Highly useful in real-world systems.

📊 Progress Tracker

Progress: 0 / 5 Completed

Done	Problem	Practice	Level	Companies
	Word Break	Solve	Medium	Amazon, Google
	Implement Trie (Prefix Tree)	Solve	Medium	Google, Uber
	Longest String with All Prefix	Solve	Medium	Google
	Phone Directory (Auto Suggest)	Solve	Medium	Google
	Longest Common Prefix	Solve	Easy	Amazon, Microsoft

🧠 Key Approaches

• Word Break: DP + Trie for faster lookup
• Trie: Insert, Search, StartsWith operations
• All Prefix String: Ensure every prefix exists
• Phone Directory: Trie + DFS for suggestions
• LCP: Traverse until first branching node

⚡ Quick Cheatsheet

Trie Node Structure

struct Node {
  Node* links[26];
  bool flag = false;
};
    

Insert Word

void insert(string word) {
  Node* node = root;
  for(char c : word) {
    if(!node->links[c-'a'])
      node->links[c-'a'] = new Node();
    node = node->links[c-'a'];
  }
  node->flag = true;
}
    

Search Prefix

bool startsWith(string pre) {
  Node* node = root;
  for(char c : pre) {
    if(!node->links[c-'a']) return false;
    node = node->links[c-'a'];
  }
  return true;
}
    

🔥 Pro Tip

Use Trie when:

• Problem involves prefixes
• Dictionary / word lookup is frequent
• Autocomplete or suggestions are required

If you see “prefix”, “dictionary”, or “auto-suggest” → think Trie instantly.

🏠 All Days ⬅ Previous Next ➡