Почему это работает
- Разбиение первых j букв кончается каким-то словом w, а перед ним разбиваются первые j − len(w) букв. Значит, ok[j] = true ровно тогда, когда за одно слово до него стоит клетка true, и если класть каждое слово от каждой клетки true, найдутся все такие.
- Одной клетки true мало: после sea остаток shell не начинается ни с одного слова, и эта ветка просто обрывается. Слово seas ведёт в ok[4], а оттуда hell доходит до конца.
- Перебор режет строку всеми способами и снова и снова пробует продолжения с одного и того же индекса. Таблица отвечает на каждый индекс один раз.
Сложность
Время O(n × слова × длина слова): из каждой из n позиций каждое слово сравнивается по буквам. Память O(n) на таблицу.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗