211. Design Add and Search Words Data Structure - Incorrect time complexity for DFS solution in articles/design-word-search-data-structure.md

[pongpatapee]

Time & Space Complexity

• Time complexity: $O(n)$ for $addWord()$, $O(n)$ for $search()$.
• Space complexity: $O(t + n)$

Where $n$ is the length of the string and $t$ is the total number of TrieNodes created in the Trie.

I noticed the solution states that time complexity for search() is O(n), but shouldn't it be O(t) instead? In the worst case, we have to traverse the entire trie.

Example

• Words in Trie: ["abc", "def", "ghi", "zzz"]
• Search: "..z" or "..p"

Assuming the Trie is searched using DFS from left to right, we would have to traverse the entire trie to get a match or see that a match doesn't exist.

Would love to hear any thoughts on this.

[Srihari2222]

@pongpatapee
Thanks for sharing, but in the constraints, there are at most 2 dots ('.') in a string. So, there is no big issue in describing it as O(t) or O(n) as it depends on different situations like the structure of the trie. But as we have at most 2 dots, it will be close to O(n).

[pongpatapee]

@Srihari2222

Oh I see, thanks for letting me know, I missed the constraint on the 2 dots. I suppose that means in the worst case it will be O(26^2 * n) , which can be simplified toO(n)? Not sure if my reasoning is entirely correct, but you're right it's definitely closer to O(n) with the 2 dots constraint.

Thanks again for your reply. Feel free to close the issue if there's nothing else to discuss.