LeetCode 648 Replace Words - Example and Complexity Analysis

Trie contains "cat", "bat", "rat". Process "cattle".

Walk through trie with "cattle":

• 'c' → exists, not a root end
• 'a' → exists, not a root end
• 't' → exists, IS a root end

Found root "cat" at length 3. Replace "cattle" with "cat".

Process "battery": 'b' → 'a' → 't' → root end. Replace with "bat".

Process "the": 't' exists but 'h' doesn't follow. No root found. Keep "the".

Build trie: $O(\sum |root|)$. Process each word: $O(|word|)$. Total: $O(n + m)$ where $n$ is total root characters and $m$ is sentence length.