用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: 我需要务实地找到subsets订单中的成员,"iamtiredareyou"即['i', 'am', 'tired', 'are', 'you']

Level-2:原始字符串可能包含序列中的一些额外字符,这些字符在子集中不存在.例如"iamtired12aareyou".在subset给定的是与上述相同,溶液应自动包括该子集在结果阵列中的正确的位置.即['i', 'am', 'tired', '12a', 'are', 'you']

我怎样才能做到这一点？

Answer 1

一般来说，递归算法就可以了。\n首先根据给定单词的开头检查所有子集，如果找到\xe2\x80\x94，则添加（追加）到找到的值，并使用单词的剩余部分和当前找到的值进行递归。\或者，如果它是字符串 \xe2\x80\x94 的末尾，则打印找到的值。

\n\n

像这样的东西：

\n\n

all=[]\ndef frec(word, values=[]):\n    gobal all\n    if word == "":  # got result.\n        all+=[values]\n    for s in subsets:\n        if word.startswith(s):\n            frec(word[len(s):], values+[s])\n\nfrec(word)\n

\n\n

请注意，由于子集包含许多单字符字符串，因此有很多可能的解决方案。您可能想要找到一些最短的结果。（13146个解决方案...使用 \xe2\x80\x9call.sort(cmp=lambda x, y: cmp(len(x), len(y)))\xe2\x80\x9d 获得最短）

\n\n

对于 level2 \xe2\x80\x94，如果没有子集匹配，则需要另一个循环，将越来越多的符号添加到下一个值（并递归到该值），直到找到匹配。

\n\n

all=[]\ndef frec(word, values=[]):\n    global all\n    if word == "":  # got result.\n        all+=[values]\n        return true\n    match = False\n    for s in subsets:\n        if word.startswith(s):\n            match = True\n            frec(word[len(s):], values+[s])       \n    if not match:                        \n        return frec(word[1:], values+[word[0]])\nfrec(word)\n

\n\n

不过，这并不尝试将非子集值合并到一个字符串中。

\n