我有一个有趣的编程难题给你:
你会得到两样东西:
包含一系列英语单词的单词,例如:
word = "iamtiredareyou"
可能的子集:
subsets = [ 'i', 'a', 'am', 'amt', 'm', 't', 'ti', 'tire', 'tired', 'i', 'ire', 'r', 're', 'red', 'redare', 'e', 'd', 'da', 'dar', 'dare', 'a', 'ar', 'are', 'r', 're', 'e', 'ey', 'y', 'yo', 'you', 'o', 'u' ]
挑战:
Level-1: 我需要务实地找到 子集
中的成员,这些成员按顺序组合在一起将构成 "iamtiredareyou"
即 ['我', '我', '累了', '是', '你']
Level-2: 原始字符串可能包含一些不在子集中的额外字符。例如“iamtired12aareyou”
。给出的 subset
与上面相同,解决方案应自动将此子集包含在结果数组的正确位置。即 ['i', 'am', 'tired', '12a', 'are', 'you']
我该怎么做?
最佳答案
一般来说,递归算法就可以了。 从检查给定单词开头的所有子集开始,如果找到 - 添加(追加)到找到的值并递归单词的剩余部分和当前找到的值。 或者,如果它是字符串的结尾 — 打印找到的值。
类似的东西:
all=[]
def frec(word, values=[]):
gobal all
if word == "": # got result.
all+=[values]
for s in subsets:
if word.startswith(s):
frec(word[len(s):], values+[s])
frec(word)
请注意,由于子集包含许多单字符字符串,因此有很多可能的解决方案。您可能想要找到一些最短的结果。 (13146 个解决方案...使用“all.sort(cmp=lambda x, y: cmp(len(x), len(y)))”得到最短的)
对于 level2 — 如果没有子集匹配,则需要另一个循环,将越来越多的符号添加到下一个值(并递归到该值),直到找到匹配为止。
all=[]
def frec(word, values=[]):
global all
if word == "": # got result.
all+=[values]
return true
match = False
for s in subsets:
if word.startswith(s):
match = True
frec(word[len(s):], values+[s])
if not match:
return frec(word[1:], values+[word[0]])
frec(word)
不过,这不会尝试将非子集值组合成一个字符串。
关于python - 用 python 解决困惑的单词拼图?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3350951/