Quiz
What is the time complexity of the following code?
from typing import List
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
root = {}
for w in wordDict:
current = root
for idx, ch in enumerate(w):
if ch not in current:
current[ch] = {}
current = current[ch]
if idx == len(w) - 1:
current["_end"] = True
nodes = [root]
for ch in s:
new_nodes = []
seen = set()
for n in nodes:
new_n = n.get(ch)
if new_n and id(new_n) not in seen:
seen.add(id(new_n))
new_nodes.append(new_n)
if "_end" in n:
new_root = root.get(ch)
if new_root and id(new_root) not in seen:
seen.add(id(new_root))
new_nodes.append(new_root)
nodes = new_nodes
return any("_end" in n for n in nodes)
Answer
O(KW + SM), where K is the mean word length, W is the number of words, S is the length of the target text, and M is the maximum word length.
Building Trie needs O(KW).
Searching the trie needs O(SM). The first loop is O(S).
Then we need to consider the size of nodes.
nodes contains all trie nodes reachable at the current position.
In the worst case, it grows to the maximum word length.
It starts with 1 element, then if it has a next element, add the next,
and if it is an end of a word, add from root.
Example: nodes grows to its maximum
Input:
-
s = "aaaaaaaaaa"(10 a's) -
wordDict = ["a", "aa", "aaa", "aaaa", "aaaaa"]- Maximum word length M=5
The trie is a straight chain of "a" nodes with depth 1 to 5.
How nodes grows on each character
Think of nodes as the set of trie depths you can be at (depth = current word length).
+--------------------+--------------+-------------------------+----------+
| Pos (1-index) | Prefix | Depths in `nodes` | #nodes |
+--------------------+--------------+-------------------------+----------+
| 1 | a | {1} | 1 |
| 2 | aa | {2, 1} | 2 |
| 3 | aaa | {3, 2, 1} | 3 |
| 4 | aaaa | {4, 3, 2, 1} | 4 |
| 5 | aaaaa | {5, 4, 3, 2, 1} | 5 |
| 6 | aaaaaa | {5, 4, 3, 2, 1} | 5 |
| 7 | aaaaaaa | {5, 4, 3, 2, 1} | 5 |
| ... | ... | ... | 5 |
+--------------------+--------------+-------------------------+----------+
What is happening?
- A "continue" step increases depth by 1 (1 → 2 → 3 → ...).
- If any node is
_end, we can "cut" and restart from root, which always reintroduces depth 1. - The trie depth is capped at M=5, so it never exceeds 5.
As a result:
- It increases by 1 at first.
- It caps at M.
- Therefore the search is O(S·M).
Quiz
Can we remove seen from the code above?
Answer
Yes, the answer is the same, but the time complexity gets worse.
For example, when multiple paths fail to match the next character, each step adds root[ch] back into nodes.
If you skip seen, you keep duplicates, so nodes can grow exponentially.
Example without seen (same input as above, M=5). The counts reflect duplicates:
+--------------------+--------------+-------------------------+----------+
| Pos (1-index) | Prefix | Depths in `nodes` | #nodes |
+--------------------+--------------+-------------------------+----------+
| 1 | a | {1} | 1 |
| 2 | aa | {2, 1} | 2 |
| 3 | aaa | {3, 2, 1, 1} | 4 |
| 4 | aaaa | {4, 3, 2, 1, 1, 1, 1} | 8 |
| 5 | aaaaa | {5, 4, 3, 2, 1, ...} | 16 |
| 6 | aaaaaa | {5, 4, 3, 2, 1, ...} | 32 |
| ... | ... | ... | 2^(n-1) |
+--------------------+--------------+-------------------------+----------+
Each _end re-adds depth 1, and without deduplication those copies keep branching.