Это вопрос : найти все (английское слово) подстроки заданной строки. (каждый = каждый, когда-либо, очень).
Очевидно, мы можем перебрать все подстроки и проверить каждый из них на английский словарь, организованный как набор. Я считаю, что словарь достаточно мал, чтобы соответствовать ОЗУ. Как организовать словарь? Что касается, как я помню, оригинальная команда spell загрузила файл words в bitmap, представляла собой набор значений хеш-слов. Я бы начал с этого.
Другим решением является trie, созданный из словаря. Используя trie, мы можем перебрать все строковые символы и проверить trie для каждого символа. Я предполагаю, что сложность этого решения в худшем случае будет одинаковой (O(n^2))
Имеет ли смысл? Предлагаете ли вы другие решения?
алгоритм сопоставления строк Aho-Corasick, который "создает конечный конечный автомат, который напоминает trie с дополнительными связями между различными внутренними узлами".
Но все, что считалось "построением три из английского словаря и одновременным поиском на нем для всех суффиксов данной строки", должно быть довольно хорошим для интервью.
Я не уверен, что Trie будет легко работать, чтобы совместить вспомогательные слова, начинающиеся в середине строки.
Другим решением с аналогичной концепцией является использование конечного автомата или регулярного выражения. регулярное выражение - это просто word1 | word2 |.... Я не уверен, что стандартные механизмы регулярных выражений могут обрабатывать выражение, охватывающее весь английский язык, но не сложно построить эквивалентный конечный автомат с учетом словаря.
После компиляции регулярного выражения\машина состояния построена, сложность анализа конкретной строки равна O (n)
Первое решение может быть уточнено, чтобы иметь другую карту хэша для каждой длины слова (для уменьшения коллизий), но кроме этого я не могу придумать ничего лучше.