python - 用 python 解决困惑的单词拼图？

Question

我有一个有趣的编程难题给你:

你会得到两样东西:

1. 包含一系列英语单词的单词，例如:

   word = "iamtiredareyou"
   

2. 可能的子集:

   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']

我该怎么做？

Answer 1

一般来说，递归算法就可以了。从检查给定单词开头的所有子集开始，如果找到 - 添加(追加)到找到的值并递归单词的剩余部分和当前找到的值。或者，如果它是字符串的结尾 — 打印找到的值。

类似的东西:

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)

不过，这不会尝试将非子集值组合成一个字符串。