如何将没有空格的文本拆分成单词列表？

Question

如何将没有空格的文本拆分成单词列表？输入： "tableapplechairtablecupboard..."很多单词将此类文本拆分为单词列表并获取的有效算法是什么？输出： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]想到的第一件事就是要经历所有可能的单词（从第一个字母开始）并找到最长的单词，继续 position=word_position+len(word)PS 我们列出了所有可能的单词。单词“橱柜”可以是“杯子”和“板子”，选择最长。语言：python，但主要的是算法本身。

Answer 1

这是使用递归搜索的解决方案：

def find_words(instring, prefix = '', words = None):

    if not instring:

        return []

    if words is None:

        words = set()

        with open('/usr/share/dict/words') as f:

            for line in f:

                words.add(line.strip())

    if (not prefix) and (instring in words):

        return [instring]

    prefix, suffix = prefix + instring[0], instring[1:]

    solutions = []

    # Case 1: prefix in solution

    if prefix in words:

        try:

            solutions.append([prefix] + find_words(suffix, '', words))

        except ValueError:

            pass

    # Case 2: prefix not in solution

    try:

        solutions.append(find_words(suffix, prefix, words))

    except ValueError:

        pass

    if solutions:

        return sorted(solutions,

                      key = lambda solution: [len(word) for word in solution],

                      reverse = True)[0]

    else:

        raise ValueError('no solution')

print(find_words('tableapplechairtablecupboard'))

print(find_words('tableprechaun', words = set(['tab', 'table', 'leprechaun'])))

产量

['table', 'apple', 'chair', 'table', 'cupboard']

['tab', 'leprechaun']