Trie

Notes and typical questions for Trie related problems

Notes

• Check the solution of LC 208 to see the template of TrieNode

  • Notice that either boolean isEnd or String word is feasible to mark a word in TrieNode

Typical Questions

• 🌟 🟠 LC 208. Implement Trie (Prefix Tree)

  • Optimal Answer.

    • Let m be the length of the word

    • TC

      • insert: $O(m)$

      • search: $O(m)$

      • prefix: $O(m)$

    • SC

      • insert: $O(m)$

      • search: $O(1)$

      • prefix: $O(1)$

• 🔴 LC 1268. Search Suggestions System

  • Code is long and it's very easy to make mistakes during the implementation

  • Optimal Answer

    • Let N be number of products, let M be the max length of the product, let L be the length of searchWord

    • TC: $O(N*M+L(L+326*(M+M))$

      • $N*M$ -> Tree Construction

      • $L*(...)$ -> for loop of each prefix of searchWord

      • $...(L+...)$ -> Find the last node of the given prefix

      • $...(M+M)$ -> Find each word takes <= $M$, call toString() of StringBuilder takes <= $M$

    • SC: $O(N*M)$

• 🟠 LC 139. Word Break

  • Maybe thinking it in a normal DP way instead of a knapsack is more clear. Be careful about the boundary.

  • This question is also put in the DP section.

  • Given $n$ as the length of s, $m$ as the length of wordDict, and $k$ as the average length of the words in wordDict

    • Straightforward DP Answer.

      • TC: $O(n^3 + m*k)$

      • SC: $O(n+m*k)$

    • Optimal Answer (DP+Trie).

      • The idea of doing dp is different from the above straightforward one.

      • TC: $O(n^2+m*k)$

      • SC: $O(n+m*k)$

• LC 211. Design Add and Search Words Data Structure

  • Let m be the length of the word

  • TC

    • addWord: $O(m)$

    • search: $O(26^m*m)$

  • SC

    • addWord: $O(m)$

    • search: $O(m)$

• 🟠 LC 212. Word Search II

  • 2 tricks for implementation.

    • Remove words from the Trie during backtracking I initially used a separate function to remove matched words from the Trie to speed up execution. However, this cleanup step can be merged directly into the DFS backtracking process, which avoids extra traversals and makes the code both more efficient and more elegant.

    • Store complete words in Trie nodes Instead of using a StringBuilder during DFS to construct the current path, a better approach is to store the full word directly in the corresponding Trie node (replacing the isEnd boolean flag). When a word is found, it can be added to the result list immediately, eliminating string reconstruction and simplifying the DFS logic.

  • Optimal Answer.

    • Assume $M$ is the number of rows, $N$ is the number of columns, $W$ is the number of words, $Lmax$ is the max word length of those words,

    • TC: $O(M*N*(4*3^{Lmax-1}))$

    • SC: $O(W*Lmax)$

• 🟠 LC 3043. Find the Length of the Longest Common Prefix

  • Damn, I should at least realize the HashMap solution. I feel so bad!

  • Approach 1 using HashMap. Answer. TC: $O(m*logm+n*logn)$, SC: $O(m*logm)$

• ⚪ LC 588. Design In-Memory File System

  • Optimal Answer.

    • TC

      • Let

        • p = length of the path string

        • k = number of non-empty components in the path (e.g. "/a/b/c" → k=3)

        • m = number of children in a directory (size of that directory’s TreeMap)

        • d = number of entries in the target directory you list (for ls on a directory)

        • c = length of the string you append in this call to addContentToFile

        • L = total length of the file content when you call readContentFromFile

      • ls()

        • File: $O(p+k*log{m})$

        • Directory: $O(p+k*log{m}+d)$

      • mkdir() : $O(p+k*log{m})$

      • addContentToFile : $O(p+k*log{m}+c)$

      • readContentFromFile : $O(p+k*log{m}+L)$

    • SC

      • Let N the total number of nodes and T be total characters across all files

      • $O(N+T)$