<p>为了获得所有可能的解决方案(如果还有一些“重叠”的单词),可以首先为每个单词找到该特定单词可能出现的所有起始位置。然后策略是从字符串的开头开始,测试可以出现在这里的所有候选字符,并将字符串中相应数量的字符向前移动。在这个新的位置,这个过程被重复(由于递归,所有的组合都被探索)。一旦我们到达字符串的末尾,就找到了一个成功的解决方案。你知道吗</p>
<pre><code>li_a = ['T', 'h','o','m','a','s','h','a','d','a','h','a','r','d','t','i','m','e','a']
li_words = ['a','The','Thomas','have','had','has','hard','hot','time','tea','timea']
def analyze(li_a, li_words):
s = ''.join(li_a)
#for each word, find all its positions in s
stat = {}
for word in li_words:
pos = s.find(word)
while pos != -1:
if not pos in stat:
stat[pos] = []
stat[pos].append(word)
pos = s.find(word, pos + 1)
solutions = []
def check(idx, solution):
if idx == len(s):
solutions.append(solution)
return
#at position idx, test all candidates and call
#itself recursively
words = stat.get(idx, [])
for word in words:
check(idx + len(word), solution + [word])
#start at the beginning
check(0, [])
return solutions
print(analyze(li_a, li_words))
</code></pre>
<p>编辑:</p>
<p>我测试了您的Unicode输入,似乎<code>string_a</code>包含一个单词<code>ဖေါ်</code>,而<code>mm-words.txt</code>中缺少这个单词。另一方面,在这种情况下,提议的解决方案无论如何都会失败。首先,在<code>pos = s.find(word, pos + len(word))</code>中有一个错误,它应该是<code>pos = s.find(word, pos + 1)</code>,以便找到特定单词的所有重叠出现。更重要的是,令人厌恶的复杂性要求(本质上是指数级的扩展)使得它在如此大的输入上无法使用。方法是采用<a href="https://stackoverflow.com/a/3469228/5351549">dynamic programming approach</a>。在下面的示例中,我只从<code>string_a</code>(保存到<code>str.txt</code>)中选取前10个单词,以避免丢失一个:</p>
<pre><code>#!/usr/bin/env python
# -*- coding: utf-8 -*-
def read_data(fname, delim, uniq = False):
with open(fname, 'r') as F:
data = F.read().split(delim)
data = map(lambda s: s.decode('utf-8').strip(), data)
data = filter(lambda s: s, data)
if uniq:
data = list(set(data))
return data
li_a = read_data('str.txt', '|')
li_words = read_data('mm-words.txt', '\n', uniq = True)
def analyze(li_a, li_words):
words = set(li_words)
s = ''.join(li_a[0:10])
N = len(s)
solutions = [ [] for idx in range(0, N) ]
S = [False for idx in range(0, N)]
for i in range(0, N):
flag = False
if (s[0:i+1] in words):
flag = True
solutions[i].append([s[0:i+1], -1])
else:
for j in range(1, i+1):
if S[j-1] and (s[j:i+1] in words):
#save the newly identified word and reference to solution
#previously found at location j-1
solutions[i].append([s[j:i+1], j-1])
#break #find only one solution
flag = True
S[i] = flag
splittings = []
def assemble(pos, L):
if pos == -1:
splittings.append(L)
return
for w,idx in solutions[pos]:
assemble(idx, [w] + L)
assemble(N-1, [])
return splittings
splittings = analyze(li_a, li_words)
for splitting in splittings:
print(' | '.join(splitting).encode('utf-8'))
</code></pre>
<p>这将产生:</p>
<pre><code>ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွတ်လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွတ်လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွတ်လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွတ်လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ်လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ်လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွတ် | လ | ပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီးခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စစ်ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စစ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လ | ပ် | တဲ့
ဒီ | စ | စ် | ဆေး | မှု | ကို | သီး | ခြား | လွ | တ် | လ | ပ် | တဲ့
</code></pre>