我有一个字典:
我需要最快的算法来解决这个问题,因为输入字符串可能会更长。
有人能解决我的问题吗?
dict = ["as", "ass", "share", "rest"]
给定一个字符串input :
string = "xassharest"
我希望展示基于此类字典的所有可能构成的单词:
[('x', 'as', 's', 'h', 'a', 'rest'), ('x', 'as', 'share', 's', 't'), ('x', 'ass', 'h', 'a', 'rest')]
实际上,我已经尝试了使用字符串的所有组合(使用itertools库),但这需要很长时间。以下是我的代码:
def getallpossiblewords(string):
allwords = preprocessingcorpus("corpus.txt")
temp = []
for i in range(0, len(string)):
for j in range(1, len(string) + 1):
if string[i:j] in allwords:
temp += [string[i:j]]
allposwords = sorted(temp, key=len, reverse=True)
#print(allposwords)
return allposwords
def wordseg(string):
a = string
b = getallpossiblewords(string)
cuts = []
allpos = []
for i in range(0,len(a)):
cuts.extend(combinations(range(1,len(a)),i))
for i in cuts:
last = 0
output = []
for j in i:
output.append(a[last:j])
last = j
output.append(a[last:])
for x in range(len(output)):
if output[x] in b:
allpos += [output]
#print(output)
#print(allpos)
fixallpos = list()
for sublist in allpos:
if sublist not in fixallpos:
fixallpos.append(sublist)
我需要最快的算法来解决这个问题,因为输入字符串可能会更长。
有人能解决我的问题吗?