鱼C论坛Python精英挑战赛（01期）挑战结果

jerryxjr1220

鱼C论坛Python精英挑战赛（01期）挑战结果公布如下：

根据各位鱼油提交的解答程序，用了6组测试数据进行比较：

1. Test = [['1', '2', '3', '4'],
   
2.         ['AB', 'BC', 'AC', 'CB', 'BA'],
   
3.         ['ABC', 'BCA', 'DAC', 'CDB', 'BDB'],
   
4.         ['ACBD', 'ADBC', 'CBDD', 'CABD'],
   
5.         ['AHCBDK', 'ADBEKC', 'ECBDGD', 'CABGHD'],
   
6.         ['ARTIST', 'TARGET', 'CARTER', 'STARTS', 'GREATS', 'EARSET']]

复制代码

比较结果如下：


综合比较下来，wei_Y的低效版的准确性更高，而高效版的执行效率更出色。所以，评选wei_Y作为优胜者。

jerryxjr1220

其实，对于这题我也写了一个，用的思路是递归插入法。
把“母字符串”拆成“head”和“tail”两部分，每次在“tail”中插入子字符串，插入完以后就归到“head”中，以此类推。

1. def solve(L):
   
2.         def gen_sub(string, tail, head=''):
   
3.                 if len(string) == 1:
   
4.                         if string in tail:
   
5.                                 return head + tail
   
6.                         else:
   
7.                                 return head + string + tail
   
8.                 else:
   
9.                         if string[0] in tail:
   
10.                                 return gen_sub(string[1:], tail[tail.find(string[0]) + 1:], head + tail[:tail.find(string[0]) + 1])
    
11.                         else:
    
12.                                 return gen_sub(string[1:], tail[:], head + string[0])
    
13.         from itertools import permutations as p
    
14.         res = []
    
15.         for each in p(L):
    
16.                 s = ''
    
17.                 for l in each:
    
18.                         s = gen_sub(l, s)
    
19.                 res.append(s)
    
20.         return min(res, key=lambda s: len(s))
    
21. 
    
22. Test = [['1', '2', '3', '4'],
    
23.         ['AB', 'BC', 'AC', 'CB', 'BA'],
    
24.         ['ABC', 'BCA', 'DAC', 'CDB', 'BDB'],
    
25.         ['ACBD', 'ADBC', 'CBDD', 'CABD'],
    
26.         ['AHCBDK', 'ADBEKC', 'ECBDGD', 'CABGHD'],
    
27.         ['ARTIST', 'TARGET', 'CARTER', 'STARTS', 'GREATS', 'EARSET']]
    
28. for test in Test:
    
29.         print(test, solve(test), len(solve(test)))

复制代码

['1', '2', '3', '4'] 4321 4
['AB', 'BC', 'AC', 'CB', 'BA'] BACB 4
['ABC', 'BCA', 'DAC', 'CDB', 'BDB'] BCDABC 6
['ACBD', 'ADBC', 'CBDD', 'CABD'] ACABDDBC 8
['AHCBDK', 'ADBEKC', 'ECBDGD', 'CABGHD'] ECABDGHCBEDKC 13
['ARTIST', 'TARGET', 'CARTER', 'STARTS', 'GREATS', 'EARSET'] GCARTEISTARGTSET 16

WelanceLee

这规则没说清楚啊，白激动半天

jerryxjr1220

WelanceLee 发表于 2017-6-19 11:30
这规则没说清楚啊，白激动半天

确实，一开始L的测试长度并没有说清楚，下次会注意，给定测试范围。
你的程序对于字符串长度短的跑出来结果都是对的，但是字符串长度长就跑不出来了。

达锅

不说限制范围才有意思

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.                 if not len(strs):
    
23.                     return t[1]+j+strs
    
24.                
    
25.                 if strs not in oldMaps:
    
26.                     tempAllRoads.append([copyList, t[1]+j])
    
27. 
    
28.                 oldMaps.add(strs)
    
29. 
    
30.         AllRoads = tempAllRoads

复制代码

准确+高效。
将最后的判断从1变为0，更加准确，多迭代一次效率上相对较低。

Teagle

下次挑战赛啥时候开始，下次我一定要夺冠！！！
这挑战赛太棒了，大佬辛苦了！！