如何將沒有空格的文本拆分成單詞列表？輸入： "tableapplechairtablecupboard..."很多單詞將此類文本拆分為單詞列表并獲取的有效算法是什么？輸出： ["table", "apple", "chair", "table", ["cupboard", ["cup", "board"]], ...]想到的第一件事就是要經歷所有可能的單詞（從第一個字母開始）并找到最長的單詞，繼續(xù) position=word_position+len(word)PS 我們列出了所有可能的單詞。單詞“櫥柜”可以是“杯子”和“板子”，選擇最長。語言：python，但主要的是算法本身。
3 回答
子衿沉夜
TA貢獻1828條經驗 獲得超3個贊
這是使用遞歸搜索的解決方案：
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']
添加回答
舉報
0/150
提交
取消