亚麻 新鲜虚拟表演

serendipity95 发表于 2020-8-26 05:45
有没有大佬可以告诉一下第二题的思路～

写个树，DFS

1. def form_words_from_pairs(pairs, word):
   
2.     # pairs.sort(key=cmp_to_key(compare))
   
3.     if len(word) > len(pairs):
   
4.         return False
   
5.     dic = {}
   
6.     for c in word:
   
7.         dic[c] = dic.get(c, 0) + 1
   
8.     return form_words_from_pairs_helper(pairs, dic, len(word))
   
9. 
   
10. 
    
11. def form_words_from_pairs_helper(pairs, dic, count):
    
12.     if not pairs:
    
13.         return True if count == 0 else False
    
14.     first, second = pairs[0][0], pairs[0][1]
    
15.     if dic.get(first, 0) != 0 and dic[first] > 0:
    
16.         dic[first] -= 1
    
17.         result = form_words_from_pairs_helper(pairs[1:], dic, count-1)
    
18.         if result:
    
19.             return result
    
20.         else:
    
21.             dic[first] += 1
    
22.     if dic.get(second, 0) != 0 and dic[second] > 0:
    
23.         dic[second] -= 1
    
24.         result = form_words_from_pairs_helper(pairs[1:], dic, count-1)
    
25.         if result:
    
26.             return result
    
27.         else:
    
28.             dic[second] += 1
    
29.     return True if count == 0 else False

复制代码

感謝樓主

my thought about 2nd Q

1. List<Node> for all pairs
2. backtracking, validate each letter