Один из вариантов - хранить все допустимые английские слова в дереве. После того, как вы это сделаете, вы можете начать идти с дерева вниз от корня, следуя буквам в строке. Всякий раз, когда вы найдете узел, помеченный как слово, у вас есть два варианта:
- Прервать ввод в этой точке или
- Продолжайте расширять слово.
Вы можете утверждать, что нашли совпадение после того, как разбили входные данные на набор слов, которые все являются допустимыми и не имеют оставшихся символов. Поскольку в каждой букве у вас есть либо одна принудительная опция (либо вы создаете слово, которое является недопустимым и должно быть остановлено - или вы можете продолжать расширять слово), либо две опции (разделение или продолжение), вы можете реализовать эту функцию с использованием исчерпывающей рекурсии:
PartitionWords(lettersLeft, wordSoFar, wordBreaks, trieNode):
// If you walked off the trie, this path fails.
if trieNode is null, return.
// If this trie node is a word, consider what happens if you split
// the word here.
if trieNode.isWord:
// If there is no input left, you're done and have a partition.
if lettersLeft is empty, output wordBreaks + wordSoFar and return
// Otherwise, try splitting here.
PartitinWords(lettersLeft, "", wordBreaks + wordSoFar, trie root)
// Otherwise, consume the next letter and continue:
PartitionWords(lettersLeft.substring(1), wordSoFar + lettersLeft[0],
wordBreaks, trieNode.child[lettersLeft[0])
В патологически худшем случае в нем будут перечислены все разделы строки, которые не могут быть экспоненциально длинными. Однако это происходит только в том случае, если вы можете разбить строку огромным количеством способов, которые начинаются с правильных английских слов, и на практике это вряд ли произойдет. Если в строке много разделов, мы могли бы потратить много времени на их поиск. Например, рассмотрим строку «dotheredo». Мы можем разделить это многими способами:
do the redo
do the red o
doth ere do
dot here do
dot he red o
dot he redo
Чтобы избежать этого, вы можете установить ограничение на количество ответов, о которых вы сообщаете, возможно, два или три.
Поскольку мы отключаем рекурсию, когда выходим из дерева, если мы когда-нибудь попробуем разделение, в котором оставшаяся часть строки не будет действительной, мы обнаружим это довольно быстро.
Надеюсь, это поможет!