Почему это работает
- У обычной буквы не больше одного потомка, куда можно пойти, поэтому поиск идёт по одному пути, как в обычном дереве.
- Точка может быть любой буквой, поэтому путём может оказаться любой потомок. match пробует их по одному и сдаётся на точке, только когда все вернули false, поэтому подходящее слово не потеряется.
- Когда шаблон кончился, на узле должна стоять отметка конца: дойти до узла — значит только, что какое-то слово так начинается.
Сложность
addWord: время O(L) для слова из L букв, память — не больше O(L) на новые узлы. search: время O(L) без точек; каждая точка может разойтись на 26 потомков, поэтому шаблон с d точками стоит до O(26^d · L). Память O(L) на стек вызовов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗