[已解决]Python：每日一题 285

zltzlt

今天的题目：

给定字符串 s，将它分割成若干回文子字符串。返回所有的分割方案。

说明：
1. 不同的方案之间的顺序可以是任意的。
2. 每种分割方案中的每个子字符串在 s 中必须是连续的。

示例 1：

输入："a"
输出：[["a"]]
解释：字符串里只有一个字符，也就只有一种分割方式 （就是它本身）。

示例 2：

输入："aab"
输出：[["aa", "b"], ["a", "a", "b"]]
解释：有两种分割的方式.
    1. 将 "aab" 分割成 "aa" 和 "b"，它们都是回文的。
    2. 将 "aab" 分割成 "a", "a" 和 "b"，它们都是回文的。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

Unicorn#

2019-12-8 00:40:01

1. record = {}
   
2. def solve(s):
   
3.     if type(s) != list:
   
4.         s = list(s)
   
5.     if str(s) in record:
   
6.         return record[str(s)]
   
7.     elif len(s) == 0:
   
8.         return [[]]
   
9.     elif len(s) == 1:
   
10.         record[str(s)] = [[s[0]]]
    
11.         return [[s[0]]]
    
12.     else:
    
13.         res = []
    
14.         temp = []
    
15.         n = len(s)
    
16.         for i in range(n):
    
17.             temp.append(s[i])
    
18.             if temp == list(reversed(temp)):
    
19.                 for solution in solve(s[i+1:]):
    
20.                     res.append([''.join(temp)]+solution)
    
21.         record[str(s)] = res
    
22.         return res

复制代码

跳转到最佳答案楼层

阴阳神万物主

抢，沙发
代码：

1. def solve(s:str)->list:
   
2.     def ishw(ts:str)->bool:#判断所给字符串是否回文
   
3.         b = list(ts)
   
4.         c = b[:]
   
5.         c.reverse()
   
6.         return b == c
   
7.     res = []
   
8.     le = len(s)
   
9.     for i in range(1,le+1):
   
10.         now = s[:i]
    
11.         if ishw(now):
    
12.             get = solve(s[i:])
    
13.             if get:
    
14.                 for each in get:
    
15.                     each.insert(0,now)
    
16.                     res.append(each[:])
    
17.             else:
    
18.                 res.append([now])
    
19.     return res
    
20. if __name__ == '__main__':
    
21.     print('示例1 输出：',solve('a'))
    
22.     print('示例2 输出：',solve('aab'))
    
23.     print('自测 输出：',solve('aabaa'))
    

复制代码

不晓得会不会过最大递归深度。
也不晓得会不会超时。

zltzlt

阴阳神万物主 发表于 2019-12-6 19:58
抢，沙发

阴阳神万物主

zltzlt 发表于 2019-12-6 19:59

话说，字符串里是只有字母吗还是怎么着？
我确认一下

zltzlt

阴阳神万物主 发表于 2019-12-6 20:01
话说，字符串里是只有字母吗还是怎么着？
我确认一下

不一定只有字母。

其实有没有字母对结果没影响。

阴阳神万物主

zltzlt 发表于 2019-12-6 19:59

已更新代码

zltzlt

阴阳神万物主 发表于 2019-12-6 19:58
抢，沙发
代码：
不晓得会不会过最大递归深度。

恭喜通过！

执行用时：1208 ms

danteer

1. def solve(s):
   
2.     if len(s) == 1:
   
3.         return [[s]]
   
4.     list1 = [i for i in s]
   
5.     result = [list1]
   
6.     for i in range(1,len(list1)-1):
   
7.         temp = 1
   
8.         templist = []
   
9.         while i - temp >= 0 and i + temp <= len(list1)-1:
   
10.             if list1[i-temp] == list1[i+temp]:
    
11.                 templist.append(temp)
    
12.                 temp += 1
    
13.             else:
    
14.                 break
    
15.         for each in templist:
    
16.             listtemp = list1.copy()
    
17.             strtemp = ''
    
18.             for j in range(2*each+1):
    
19.                 strtemp += listtemp.pop(i-each)
    
20.             listtemp.insert(i-each,strtemp)
    
21.             result.append(listtemp)
    
22.     for i in range(0,len(list1)-1):
    
23.         if list1[i] == list1[i+1]:
    
24.             temp = 1
    
25.             templist = [0]
    
26.             while i - temp >= 0 and i + temp + 1 <= len(list1)-1:
    
27.                 if list1[i-temp] == list1[i+temp+1]:
    
28.                     templist.append(temp)
    
29.                     temp += 1
    
30.                 else:
    
31.                     break
    
32.             for each in templist:
    
33.                 listtemp = list1.copy()
    
34.                 strtemp = ''
    
35.                 for j in range(2*each+2):
    
36.                     strtemp += listtemp.pop(i-each)
    
37.                 listtemp.insert(i-each,strtemp)
    
38.                 result.append(listtemp)
    
39.     return result

复制代码

没有递归，速度应该没问题

zltzlt

danteer 发表于 2019-12-6 20:51
没有递归，速度应该没问题

解答错误

输入："cbbbcc"
输出：[["cbbbc","c"],["c","bbb","c","c"],["c","b","b","b","cc"],["c","b","bb","c","c"],["c","bb","b","c","c"],["c","b","b","b","c","c"]]
预期结果：[["cbbbc","c"],["c","bbb","cc"],["c","b","bb","cc"],["c","bb","b","cc"],["c","bbb","c","c"],["c","b","b","b","cc"],["c","b","bb","c","c"],["c","bb","b","c","c"],["c","b","b","b","c","c"]]

hrp

不好意思没看懂题

zltzlt

hrp 发表于 2019-12-6 22:03
不好意思没看懂题

将一个字符串分割成若干个子字符串，每个子字符串都是回文字符串，求所有的分割方案。

danteer

1. def solve(s):
   
2.     if len(s) == 1:
   
3.         return [[s]]
   
4.     list1 = [i for i in s]
   
5.     result = [list1]
   
6.     for i in range(1,len(list1)-1):
   
7.         temp = 1
   
8.         templist = []
   
9.         while i - temp >= 0 and i + temp <= len(list1)-1:
   
10.             if list1[i-temp] == list1[i+temp]:
    
11.                 templist.append(temp)
    
12.                 temp += 1
    
13.             else:
    
14.                 break
    
15.         for each in templist:
    
16.             listtemp = list1.copy()
    
17.             strtemp = ''
    
18.             for j in range(2*each+1):
    
19.                 strtemp += listtemp.pop(i-each)
    
20.             listtemp.insert(i-each,strtemp)
    
21.             st = ''
    
22.             for j in listtemp[i-each+1:]:
    
23.                 st += j
    
24.             lst = solve(st)
    
25.             for j in range(len(lst)):
    
26.                 lst[j] = listtemp[:i-each+1] + lst[j]
    
27.             result.extend(lst)
    
28.     for i in range(0,len(list1)-1):
    
29.         if list1[i] == list1[i+1]:
    
30.             temp = 1
    
31.             templist = [0]
    
32.             while i - temp >= 0 and i + temp + 1 <= len(list1)-1:
    
33.                 if list1[i-temp] == list1[i+temp+1]:
    
34.                     templist.append(temp)
    
35.                     temp += 1
    
36.                 else:
    
37.                     break
    
38.             for each in templist:
    
39.                 listtemp = list1.copy()
    
40.                 strtemp = ''
    
41.                 for j in range(2*each+2):
    
42.                     strtemp += listtemp.pop(i-each)
    
43.                 listtemp.insert(i-each,strtemp)
    
44.                 st = ''
    
45.                 for j in listtemp[i-each+1:]:
    
46.                     st += j
    
47.                 lst = solve(st)
    
48.                 for j in range(len(lst)):
    
49.                     lst[j] = listtemp[:i-each+1] + lst[j]
    
50.                 result.extend(lst)
    
51.     return result

复制代码

闲愚

这个应该没问题，就是有可能会超时

1. def judge_str(s):
   
2.     n = len(s)
   
3.     result = 0
   
4.     judge_list = []
   
5.     if n == 1:
   
6.         result = 1
   
7.     else:
   
8.         for i in range(n // 2):
   
9.             if s[i] == s[n - i - 1]:
   
10.                 judge_list.append(1)
    
11.             else:
    
12.                 judge_list.append(0)
    
13.         if 0 not in judge_list:
    
14.             result = 1
    
15.     return result
    
16. 
    
17. def split_str(s,k):
    
18.     n = len(s)
    
19.     result = []
    
20.     if k > 1:
    
21.         for i in range(n - k + 1):
    
22.             if n > k:
    
23.                 new_s = s[i + 1:]
    
24.                 comb = split_str(new_s,k - 1)
    
25.                 for item in comb:
    
26.                     item.insert(0, s[:i + 1])
    
27.                     result.append(item)
    
28.             else:
    
29.                 list1 = []
    
30.                 for i in range(n):
    
31.                     list1.append(s[i])
    
32.                 result.append(list1)
    
33.     else:
    
34.         result.append([s])
    
35.     return result
    
36. 
    
37. str1 = 'cbbbcc'
    
38. n = len(str1)
    
39. for i in range(n):
    
40.     list1 = split_str(str1,i + 1)
    
41.     for member in list1:
    
42.         list2 = []
    
43.         for item in member:
    
44.             list2.append(judge_str(item))
    
45.         if 0 not in list2:
    
46.             print(member)

复制代码

peicd

1. import itertools
   
2. def abc(st):
   
3.     wzzh,result,length=[],[],len(st)
   
4.     for i in range(length):
   
5.         for j in itertools.combinations(range(1,length),i):
   
6.             wzzh.append([0]+list(j)+[length])
   
7.     for each in wzzh:
   
8.         ls=[]
   
9.         for i in range(len(each)-1):
   
10.             m,n=each[i],each[i+1]
    
11.             zhifu= st[m:n]
    
12.             if zhifu==zhifu[::-1]:
    
13.                 ls.append(st[m:n])
    
14.             else:
    
15.                 ls=[]
    
16.                 break
    
17.         if ls!=[]:
    
18.             result.append(ls)
    
19.     return  result

复制代码

18463102026

1. def fun(s):
   
2.     def chazhao(s):
   
3.         '返回索引从0开始满足条件的回文序列的所有长度生成器'
   
4.         n = 1
   
5.         while n<=len(s):
   
6.             s1 = s[:n]
   
7.             if s1 == s1[::-1]:
   
8.                 yield n
   
9.             n += 1
   
10.     for i in chazhao(s):
    
11.         if i == len(s):
    
12.             yield s.split(',')
    
13.         else:
    
14.             yield from [s[:i].split(',')+j for j in fun(s[i:])]
    
15. 
    
16. 
    
17. 
    
18. s1 = 'cbbbcc'
    
19. s1_out =[ i for i in fun(s1)]
    
20. s2 = 'aabbbc'
    
21. s2_out =[ i for i in fun(s2)]
    
22. 
    
23. print(f"输入：{s1}\n输出：{s1_out}")
    
24. print(f"输入：{s2}\n输出：{s2_out}")
    
25. 
    
26. >>>
    
27. ================== RESTART: C:\Users\13555\Desktop\每日一题.py ==================
    
28. 输入：cbbbcc
    
29. 输出：[['c', 'b', 'b', 'b', 'c', 'c'], ['c', 'b', 'b', 'b', 'cc'], ['c', 'b', 'bb', 'c', 'c'], ['c', 'b', 'bb', 'cc'], ['c', 'bb', 'b', 'c', 'c'], ['c', 'bb', 'b', 'cc'], ['c', 'bbb', 'c', 'c'], ['c', 'bbb', 'cc'], ['cbbbc', 'c']]
    
30. 输入：aabbbc
    
31. 输出：[['a', 'a', 'b', 'b', 'b', 'c'], ['a', 'a', 'b', 'bb', 'c'], ['a', 'a', 'bb', 'b', 'c'], ['a', 'a', 'bbb', 'c'], ['aa', 'b', 'b', 'b', 'c'], ['aa', 'b', 'bb', 'c'], ['aa', 'bb', 'b', 'c'], ['aa', 'bbb', 'c']]
    
32. >>>

复制代码

zltzlt

闲愚 发表于 2019-12-7 13:37
这个应该没问题，就是有可能会超时

输入 "amanaplanacanalpanama" 超时

zltzlt

peicd 发表于 2019-12-7 15:52

输入 "amanaplanacanalpanama" 超时

zltzlt

18463102026 发表于 2019-12-7 19:16

恭喜通过！

执行用时：1185 ms

zltzlt

danteer 发表于 2019-12-7 09:39

恭喜通过！

执行用时：1143 ms

Unicorn#

1. record = {}
   
2. def solve(s):
   
3.     if type(s) != list:
   
4.         s = list(s)
   
5.     if str(s) in record:
   
6.         return record[str(s)]
   
7.     elif len(s) == 0:
   
8.         return [[]]
   
9.     elif len(s) == 1:
   
10.         record[str(s)] = [[s[0]]]
    
11.         return [[s[0]]]
    
12.     else:
    
13.         res = []
    
14.         temp = []
    
15.         n = len(s)
    
16.         for i in range(n):
    
17.             temp.append(s[i])
    
18.             if temp == list(reversed(temp)):
    
19.                 for solution in solve(s[i+1:]):
    
20.                     res.append([''.join(temp)]+solution)
    
21.         record[str(s)] = res
    
22.         return res

复制代码