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

挑战：

第一关： 我需要找出在 subsets 中的单词，按照一定的顺序组合起来，能形成 "iamtiredareyou"，也就是 ['i', 'am', 'tired', 'are', 'you']。

第二关： 原始字符串可能会包含一些不在单词组合中的额外字符，比如 "iamtired12aareyou"。给定的 subset 和上面的一样，解决方案应该能自动把这个单词组合放在结果数组的正确位置，也就是 ['i', 'am', 'tired', '12a', 'are', 'you']。

我该怎么做呢？

Answer 1

对于这个一级挑战，你可以用递归的方法来解决。虽然这可能不是最有效的办法，但确实是最简单的：

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

def findsubset():
    global word

    for subset in subsets:
        if word.startswith(subset):
            setlist.append(subset)
            word = word[len(subset):]

            if word == "":
                print setlist
            else:
                findsubset()

            word = subset + word
            setlist.pop()

# Remove duplicate entries by making a set
subsets = set(subsets)
setlist = []
findsubset()

你的子集列表中有重复的元素，比如说'a'出现了两次。所以我的代码会把它变成一个set，这样就能在查找结果之前去掉重复的部分。

Answer 2

我觉得你应该自己动手做一些编程练习……

Answer 3

一般来说，递归算法就可以解决这个问题。首先检查所有可能的子集，看看它们是否和给定单词的开头匹配。如果找到了，就把这个匹配的结果加到已找到的值里，然后继续用剩下的部分和当前找到的值进行递归处理。如果到了字符串的末尾，就打印出找到的值。

大概是这样的：

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)))”来获取最短的结果）

对于第二级别的情况，如果没有子集匹配，你需要再加一个循环，这个循环会不断添加更多的符号到下一个值中（并进行递归处理），直到找到匹配为止。

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)

不过，这个方法并不会尝试把非子集的值组合成一个字符串。