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

個

挑戰：

1級：我需要以務實的態度尋找成員subsets一起在訂單將使"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 - 您需要另一個循環if沒有任何子集匹配將越來越多的符號添加到下一個值（並遞歸到該值）直到找到匹配。

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) 

雖然這並不嘗試將非子集值組合到一個字符串中。

Answer 2

我認爲你應該做你自己的編程excercises ....

Answer 3

對於你能做到這一點recursively 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 4

是不是就像找到排列一樣，但有一些條件？就像你開始排列算法（遞歸的）一樣，你檢查你已經擁有的字符串是否與你的第一個X字符相匹配，如果是的話，你繼續遞歸直到找到整個單詞，否則你回去。

如果你問我，等級2有點傻，因爲那麼你實際上可以寫任何東西作爲「要找到的單詞」，但基本上它會像level1一樣，但是如果你找不到子字符串在你的列表中，你只需添加它（逐字母即你有「愛」和你匹配'l'的['l'，'e']的列表，但你缺少'o'，所以你添加它並檢查是否有你的單詞在列表中以'v'開始，並且匹配你的單詞以找到它們，但它們不會將'v'添加到'o'等）。

如果你感到無聊，你可以實現一個遺傳算法，這真的很有趣，但不是很有效。

Answer 5

這裏是一個遞歸的，低效的Java解決方案：

private static void findSolutions(Set<String> fragments, String target, HashSet<String> solution, Collection<Set<String>> solutions) { 
    if (target.isEmpty()) { 
     solutions.add(solution); 
     return; 
    } 

    for (String frag : fragments) { 
     if (target.startsWith(frag)) { 
      HashSet<String> solution2 = new HashSet<String>(solution); 
      solution2.add(frag); 
      findSolutions(fragments, target.substring(frag.length()), solution2, solutions); 
     } 
    }  
} 

public static Collection<Set<String>> findSolutions(Set<String> fragments, String target) { 
    HashSet<String> solution = new HashSet<String>(); 
    Collection<Set<String>> solutions = new ArrayList<Set<String>>(); 
    findSolutions(fragments, target, solution, solutions); 
    return solutions; 
} 

Answer 6

對不起缺乏編程片斷的，但我想建議動態規劃。攻擊等級1和等級2同時給每個單詞賦予一個成本，並且將不存在的所有單個字符添加爲單個字符的高成本單詞。然後問題是找到將序列分解成單詞的方式，從而以最小的總成本。

沿着順序從左到右工作，在每個點工作並節省最少成本的解決方案直到幷包括當前點，以及結束該解決方案的單詞的長度。爲了找出序列中下一個點的答案，考慮所有已知的詞，它們是序列的後綴。對於每個這樣的單詞，通過將該單詞的成本加入到該單詞開始之前結束的最佳解決方案的（已經計算出的）成本中來計算出最佳總成本。請注意最小的總成本和生成它的單詞的長度。

一旦您對整個序列的成本最高，請使用該序列中最後一個單詞的長度來計算出最後一個單詞的最後一個單詞，然後退回該字符數以檢查在該單元中計算出的答案指出並得到最後一個單詞前面的單詞，依此類推。