[已解决]鱼C论坛python挑战赛（01期）

jerryxjr1220

Python的编程技能还是要靠平时不断地练习才能提高，为了提高大家的积极性，特别设立了这个挑战赛，希望大家多多参与！

第一个解答本题的鱼油奖励100鱼币，本期挑战赛限时3天，截至日：6月18日24时，参赛人员：python论坛任何人员（包括版主）。

另外，如果有创意的解题方法或者优雅的代码，会酌情追加奖励！

本期题目：

给定一个列表L，例如：['ACBD','ADBC','CBDD','CABD']，包含有n组字符串。

通过下图，可以发现，最后一行的字符串包含了列表L中所有字符串，也就是说L中所有字符串都是最后一行字符串的“子字符串”（未必连续），这最后一行字符串称作为“母字符串”。

1. 
   
2. A C    B D
   
3. A        D B C
   
4.    C   B D    D
   
5.    C A B D
   
6. ===============
   
7. A C A B D B C D
   

复制代码

现在请通过给定的列表L，求出最短的包含L中所有字符串的“母字符串”的长度。

例如：
L = ['ACBD','ADBC','CBDD','CABD']
输出：8

@冬雪雪冬 @SixPy @～风介～

感谢小甲鱼老师倾情赞助！

本期挑战结束，挑战结果见http://bbs.fishc.com/thread-89179-1-1.html

本界挑战赛，共设5场比赛，每周安排1~2场，每场挑战赛为期3天，每场比赛奖励100鱼币，同时会给优秀代码增加额外奖励！

02期即将开始，欢迎大家踊跃参与！

最佳答案

月排行榜 / 总排行榜

wei_Y

2017-6-15 19:08:48

1. def combinations(rawList):
   
2.     AllRoads = [[rawList, '']]
   
3. 
   
4.     oldMaps = set()
   
5.    
   
6.     while 1:
   
7.         tempAllRoads = []
   
8.         
   
9.         for t in AllRoads:
   
10.             currentWords = {i[0] for i in t[0] if i}
    
11. 
    
12.             for j in currentWords:
    
13.                 # 字符串不需要深拷贝。
    
14.                 copyList = t[0].copy()
    
15.                
    
16.                 for index, data in enumerate(copyList):
    
17.                     if data:
    
18.                         if data[0] == j:
    
19.                             copyList[index] = data[1:]
    
20. 
    
21.                 strs = ''.join(copyList)
    
22. 
    
23.                 if len(strs) == 1:
    
24.                     return t[1]+j+strs
    
25.                
    
26.                 if strs not in oldMaps:
    
27.                     tempAllRoads.append([copyList, t[1]+j])
    
28. 
    
29.                 oldMaps.add(strs)
    
30. 
    
31.         AllRoads = tempAllRoads

复制代码

优化版本。基本思路是根据 广度优先算法来的。

跳转到最佳答案楼层

wei_Y

1. def combinations(rawList):
   
2.     AllRoads = [[rawList, '']]
   
3. 
   
4.     oldMaps = set()
   
5.    
   
6.     while 1:
   
7.         tempAllRoads = []
   
8.         
   
9.         for t in AllRoads:
   
10.             currentWords = {i[0] for i in t[0] if i}
    
11. 
    
12.             for j in currentWords:
    
13.                 # 字符串不需要深拷贝。
    
14.                 copyList = t[0].copy()
    
15.                
    
16.                 for index, data in enumerate(copyList):
    
17.                     if data:
    
18.                         if data[0] == j:
    
19.                             copyList[index] = data[1:]
    
20. 
    
21.                 strs = ''.join(copyList)
    
22. 
    
23.                 if len(strs) == 1:
    
24.                     return t[1]+j+strs
    
25.                
    
26.                 if strs not in oldMaps:
    
27.                     tempAllRoads.append([copyList, t[1]+j])
    
28. 
    
29.                 oldMaps.add(strs)
    
30. 
    
31.         AllRoads = tempAllRoads

复制代码

优化版本。基本思路是根据 广度优先算法来的。

jerryxjr1220

大家踊跃答题哦，可以提供一些思路，未必肯定正确，供大家参考。
如果把L中的字符串全部连起来构成的“母字符串”肯定包含所有“子字符串”，但是未必最短。
然后可以想办法删除“母字符串”中的字符，看哪些字符删除后，“母字符串”依然成立，以此来缩短“母字符串”的长度。

ooxx7788

可不可以调整L里面字符串的顺序呢？比如变成C开头，这个好像没有说清楚。

jerryxjr1220

ooxx7788 发表于 2017-6-15 22:22
可不可以调整L里面字符串的顺序呢？比如变成C开头，这个好像没有说清楚。

列表L里面的n个字符串在L中的位置可以调整，也就是可以对L进行sort（）操作，不会影响最后结果。
但是这些字符串中的字母顺序是不能改变的。

jerryxjr1220

再给一些提示，我写了一个判断子字符串s是否在母字符串strings中的函数，当然，这仅供参考，未必一定有用。

1. def is_sub(s, strings):
   
2.     if len(s) == 1 and s in strings:
   
3.         return True
   
4.     if s[0] not in strings:
   
5.         return False
   
6.     return is_sub(s[1:], strings[strings.find(s[0])+1:])

复制代码

jerryxjr1220

大家加油！100鱼币在向你招手！

SixPy

jerryxjr1220 发表于 2017-6-16 13:04
大家加油！100鱼币在向你招手！

早就写好了，不想发，怕影响其他人的思路。
等等看~

SixPy

你这题难度有点高啊，曲高和寡~

类似这种有奖竞答的题目，鱼币应该由论坛出吧，不应该由出题者支出。
@小甲鱼 @康小泡 @～风介～

jerryxjr1220

SixPy 发表于 2017-6-16 18:59
你这题难度有点高啊，曲高和寡~

类似这种有奖竞答的题目，鱼币应该由论坛出吧，不应该由出题者支出。

谁出鱼币无所谓的，反正我有好多鱼币也用不掉，无非是提高一点大家的积极性！
这次是第一期，题目难度还需要摸索，怕太简单，几分钟就被解决了

WelanceLee

1. L = ['ACBD','ADBC','CBDD','CABD']
   
2. result = []
   
3. 
   
4. def check(l):
   
5.     for each in l:
   
6.         if each != '':
   
7.             return False
   
8.     return True
   
9. 
   
10. def poplist(l):
    
11.     x = []
    
12.     for each in l:
    
13.         if each != '':
    
14.             x.append(each[0])
    
15.     x = list(set(x))
    
16.     x.sort()
    
17.     return x
    
18. 
    
19. def dele(l, x):
    
20.     y = [ ]
    
21.     for each in l:
    
22.         if each == '':
    
23.             y.append(each)
    
24.         else:
    
25.             if each[0] == x:
    
26.                 y.append(each[1:])
    
27.             else:
    
28.                 y.append(each)
    
29.     return y
    
30. 
    
31. 
    
32. def dfs(step, l):
    
33.     if check(l):
    
34.         result.append(step)
    
35.         return
    
36.     x = poplist(l)
    
37.     for each in x:
    
38.         lx = dele(l, each)
    
39.         dfs(step+1, lx)
    
40.         
    
41. dfs(0, L)
    
42. print(min(result))

复制代码

SixPy

WelanceLee 发表于 2017-6-16 20:09

L = ['AhCBDk','ADBekC','eCBDgD','CABghD']

用你的程序试试这个~

～风介～

SixPy 发表于 2017-6-16 18:59
你这题难度有点高啊，曲高和寡~

类似这种有奖竞答的题目，鱼币应该由论坛出吧，不应该由出题者支出。

我记得数据结构课程里面好像有这个题目来着，只是忘记了~

Teagle

心累啊，方法有点笨，接近十二个小时
丫的，今天还要考四级，要是得不到这100鱼币，我就要崩溃了。

1. # 基列表挑选准则：挑选含不同字母多的字符串
   
2. def base(a):
   
3.     c = []
   
4.     for i in range(len(a)):
   
5.         c.append(len(set(a[i])))
   
6.     return (c.index(max(c))) #返回符合要求的字符串在列表中的位置
   
7. 
   
8. # 次列表的挑选准则：挑选字母在基列表中位置靠前的字符串，如果没有则选择第一个字符串
   
9. def less(a,a_base):
   
10.     if len(a) == 1:
    
11.         return 0
    
12.     else:
    
13.         temp = []
    
14.         for i in a_base:
    
15.             for j in range(len(a)):
    
16.                 try:
    
17.                     temp.append(a[j].index(i))
    
18.                 except ValueError:
    
19.                     temp.append(len(a[j]))
    
20.             if min(temp)<len(a[j]):
    
21.                 return(temp.index(min(temp))) #返回符合要求的字符串在列表中的位置
    
22.         return 0 #如果没有与基列表重复的字母，则选择第一个字符串
    
23. 
    
24. # 寻找所有的匹配组合，返回匹配超度最长的组合。
    
25. def seek_index(a_base,a_less):
    
26.     #返回在主列表中的位置T=[组合1,..,组合n] 组合1=[位置0,...,位置n]
    
27.     T = []
    
28.     for i in range(len(a_less)):
    
29.         temp = []        
    
30.         for j in range(i,len(a_less)):
    
31.             if temp==[]:
    
32.                 k=0
    
33.             try:
    
34.                 k = a_base.index(a_less[j],k)
    
35.                 temp.append(k) #偶数位置是对应元素在基列表中的位置
    
36.                 temp.append(j) #奇数位置是对应元素在次列表中的位置
    
37.                 k += 1
    
38.             except ValueError:
    
39.                 pass
    
40.             
    
41.         T.append(temp)
    
42.     #返回最长组合
    
43.     temp = []
    
44.     for k in T:        
    
45.         temp.append(len(k))
    
46.     return (T[temp.index(max(temp))])
    
47. 
    
48. #利用得到的最优匹配位置进行匹配，在基列表中插入不满足次列表的元素
    
49. def match(a_base,a_less,index):
    
50. 
    
51.     temp_base = []
    
52.     temp_less = []
    
53.     for i in range(len(index)):
    
54.         if not i % 2:
    
55.             temp_base.append(index[i])#得到对应元素在基列表中的位置
    
56.         else:
    
57.             temp_less.append(index[i])#得到对应元素在次列表中的位置
    
58. 
    
59.     for i in range(len(temp_less)):
    
60.         if temp_less[i] != 0:
    
61.             if i == 0:
    
62.                 temp = a_less[:temp_less[i]]
    
63.                 temp.reverse()
    
64.                 for j in range(len(temp)):
    
65.                     a_base.insert(temp_base[i],temp[j])
    
66.             elif i != len(a_less) - 1 and temp_less[i] - temp_less[i-1] > 1:
    
67.                 temp = a_less[temp_less[i-1]+1:temp_less[i]]
    
68.                 temp.reverse()
    
69.                 for j in range(len(temp)):
    
70.                     a_base.insert(temp_base[i],temp[j])
    
71.             elif i == len(temp_less) -1 and i != len(a_less) - 1 and temp_less[i] - temp_less[i-1] == 1:
    
72.                 temp = a_less[temp_less[i]+1:]
    
73.                 for j in range(len(temp)):
    
74.                     a_base.append(temp[j])
    
75. 
    
76.     return a_base            
    
77.         
    
78.    
    
79. L = ['ACBD','ADBC','CBDD','CABD']
    
80. 
    
81. list_base = list(L[base(L)]) # 挑选基列表
    
82. L.remove(''.join(list_base)) # 在L中移除选中的基列表所对应的字符串
    
83. 
    
84. for i in range(len(L)):
    
85.     list_less = list(L[less(L,list_base)]) #挑选次列表
    
86.     L.remove(''.join(list_less))# 在L中移除选中的次列表中对应的字符串
    
87.     nice_index = seek_index(list_base,list_less) #查找最佳匹配顺序
    
88.     list_base = match(list_base,list_less,nice_index) #进行匹配   
    
89. 
    
90. 
    
91. print (len(list_base))
    
92. 
    
93. 
    
94. 
    
95. 
    
96.                
    
97. 
    
98. 
    
99. 
    
100. 
     
101. 
     
102. 
     
103. 
     
104. 
     
105. 
     
106. 
     
107. 
     
108. 
     
109. 
     
110. 
     
111. 
     
112. 
     
113. 
     
114. 
     
115. 
     
116. 
     
117. 
     
118. 
     
119. 
     
120. 
     
121. 
     
122. 
     
123. 
     
124. 
     
125. 
     
126. 
     

复制代码

Teagle

SixPy 发表于 2017-6-16 21:01
L = ['AhCBDk','ADBekC','eCBDgD','CABghD']

用你的程序试试这个~

1. ['A', 'h', 'e', 'C', 'A', 'g', 'h', 'B', 'D', 'B', 'e', 'k', 'g', 'D']
   
2. 14

复制代码

小甲鱼

SixPy 发表于 2017-6-16 18:59
你这题难度有点高啊，曲高和寡~

类似这种有奖竞答的题目，鱼币应该由论坛出吧，不应该由出题者支出。

嗯嗯，可以的，支持此类互动！

小甲鱼

jerryxjr1220 发表于 2017-6-15 22:03
大家踊跃答题哦，可以提供一些思路，未必肯定正确，供大家参考。
如果把L中的字符串全部连起来构成的“母 ...

支持楼主，可以创建一个淘专辑，将此类活动汇集起来，方便后来者学习~

jerryxjr1220

小甲鱼 发表于 2017-6-17 03:29
支持楼主，可以创建一个淘专辑，将此类活动汇集起来，方便后来者学习~

感谢老大支持！
挑战结果会在挑战期限之后公布，同时会归类到淘专辑

jerryxjr1220

Teagle 发表于 2017-6-17 02:44

你再看看，好像你的母字符串并没有全部包含子字符串哦

Teagle

jerryxjr1220 发表于 2017-6-17 06:26
你再看看，好像你的母字符串并没有全部包含子字符串哦

怎么可能没有呢