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

zltzlt

今天的题目：

给出三个字符串：s1、s2、s3，判断 s3 是否由 s1 和 s2 交叉构成。

示例 1：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：True

示例 2：

输入：s1 = "", s2 = "", s3 = "1"
输出：False

示例 3：

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：False

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

塔利班

2019-11-2 09:05:38

1. def dp(s1,s2,s3):
   
2.     if not (s1 and s2 and s3):
   
3.         return s3==s1+s2
   
4.     else:
   
5.         if s3[0]==s1[0] and s3[0]==s2[0]:
   
6.             return dp(s1[1:],s2,s3[1:])or dp(s1,s2[1:],s3[1:])
   
7.         elif s3[0]==s1[0]:
   
8.             return dp(s1[1:],s2,s3[1:])
   
9.         elif s3[0]==s2[0]:
   
10.             return dp(s1,s2[1:],s3[1:])
    
11.         else:
    
12.             return False
    

复制代码

跳转到最佳答案楼层

塔利班

1. def dp(s1,s2,s3):
   
2.     if not (s1 and s2 and s3):
   
3.         return s3==s1+s2
   
4.     else:
   
5.         if s3[0]==s1[0] and s3[0]==s2[0]:
   
6.             return dp(s1[1:],s2,s3[1:])or dp(s1,s2[1:],s3[1:])
   
7.         elif s3[0]==s1[0]:
   
8.             return dp(s1[1:],s2,s3[1:])
   
9.         elif s3[0]==s2[0]:
   
10.             return dp(s1,s2[1:],s3[1:])
    
11.         else:
    
12.             return False
    

复制代码

zltzlt

塔利班 发表于 2019-11-2 09:05

恭喜通过！

执行用时：101 ms

122815306

def s1_s2(s1,s2,s3):
    new_s = s1 + s2
    for s in new_s:
        if s in s3:
            new_s3 = s3.replace(s,'',1)
            s3 = new_s3
        else:
            return False
    if new_s3 == '':
        return True
    else:
        return False

阴阳神万物主

搞定咯！
我刚才在搞什么哦！

1. def solve(s1:str,s2:str,s3:str)->bool:
   
2.     if len(s3) != len(s1+s2):
   
3.         print('调试',1)
   
4.         return False
   
5.     a=set(s1+s2)
   
6.     for i in a:
   
7.         if s1.count(i) + s2.count(i) != s3.count(i):
   
8.             print('调试',2)
   
9.             return False
   
10.     s1,s2,s3 = list(s1),list(s2),list(s3)
    
11.     begin = True
    
12.     changed = False
    
13.     while s1 and s2:
    
14.         if s3[0] == s1[0]:
    
15.             if begin:
    
16.                 begin = False
    
17.                 flg = 1
    
18.             elif flg == 2:
    
19.                 changed = True
    
20.             s1.pop(0)
    
21.         elif s3[0] == s2[0]:
    
22.             if begin:
    
23.                 begin = False
    
24.                 flg = 2
    
25.             elif flg == 1:
    
26.                 changed = True
    
27.             s2.pop(0)
    
28.         else:
    
29.             print('调试',3)
    
30.             return False
    
31.         s3.pop(0)
    
32.     else:
    
33.         print('调试',4)
    
34.         return changed
    
35. 
    
36. if __name__ == '__main__':
    
37.     print('示例1 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"))
    
38.     print('示例2 输出：',solve(s1 = "", s2 = "", s3 = "1"))
    
39.     print('示例3 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
    
40. 
    

复制代码

二楼那个，不考虑最大递归深度吗

zltzlt

122815306 发表于 2019-11-2 11:23
def s1_s2(s1,s2,s3):
    new_s = s1 + s2
    for s in new_s:

输入 s1 = '', s2 = '', s3 = '' 出错

zltzlt

阴阳神万物主 发表于 2019-11-2 12:05
搞定咯！
我刚才在搞什么哦！

解答错误

输入：s1 = "", s2 = "", s3 = ""
打印：调试 4
输出：False
预期结果：True

阴阳神万物主

zltzlt 发表于 2019-11-2 12:32
解答错误

输入：s1 = "", s2 = "", s3 = ""

哦，原来全为空认定为交叉啊

阴阳神万物主

zltzlt 发表于 2019-11-2 12:32
解答错误

输入：s1 = "", s2 = "", s3 = ""

加上特殊处理，完事儿

1. def solve(s1:str,s2:str,s3:str)->bool:
   
2.     if len(s3) != len(s1+s2):
   
3.         #print('调试',1)
   
4.         return False
   
5.     elif not(len(s1)and len(s2)and len(s3)):
   
6.         #print('调试',5)
   
7.         return True
   
8.     a=set(s1+s2)
   
9.     for i in a:
   
10.         if s1.count(i) + s2.count(i) != s3.count(i):
    
11.             #print('调试',2)
    
12.             return False
    
13.     s1,s2,s3 = list(s1),list(s2),list(s3)
    
14.     begin = True
    
15.     changed = False
    
16.     while s1 and s2:
    
17.         if s3[0] == s1[0]:
    
18.             if begin:
    
19.                 begin = False
    
20.                 flg = 1
    
21.             elif flg == 2:
    
22.                 changed = True
    
23.             s1.pop(0)
    
24.         elif s3[0] == s2[0]:
    
25.             if begin:
    
26.                 begin = False
    
27.                 flg = 2
    
28.             elif flg == 1:
    
29.                 changed = True
    
30.             s2.pop(0)
    
31.         else:
    
32.             #print('调试',3)
    
33.             return False
    
34.         s3.pop(0)
    
35.     else:
    
36.         #print('调试',4)
    
37.         return changed
    
38. 
    
39. if __name__ == '__main__':
    
40.     print('示例1 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"))
    
41.     print('示例2 输出：',solve(s1 = "", s2 = "", s3 = "1"))
    
42.     print('示例3 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
    

复制代码

zltzlt

阴阳神万物主 发表于 2019-11-2 12:52
加上特殊处理，完事儿

输入：s1 = "aa", s2 = "a", s3 = "aaa"
输出：False
预期结果：True

阴阳神万物主

zltzlt 发表于 2019-11-2 12:55
输入：s1 = "aa", s2 = "a", s3 = "aaa"
输出：False
预期结果：True

这回，也许、大概没问题了

1. def solve(s1:str,s2:str,s3:str)->bool:
   
2.     if len(s3) != len(s1+s2):
   
3.         print('调试',1)
   
4.         return False
   
5.     elif not(len(s1)and len(s2)and len(s3)):
   
6.         print('调试',5)
   
7.         return True
   
8.     a=set(s1+s2)
   
9.     for i in a:
   
10.         if s1.count(i) + s2.count(i) != s3.count(i):
    
11.             print('调试',2)
    
12.             return False
    
13.     s1,s2,s3 = list(s1),list(s2),list(s3)
    
14.     begin = True
    
15.     changed = False
    
16.     while s1 and s2:
    
17.         if begin:
    
18.             if s3[0] == s1[0]:
    
19.                 begin = False
    
20.                 flg = 1
    
21.                 s1.pop(0)
    
22.             elif s3[0] == s2[0]:
    
23.                 begin = False
    
24.                 flg = 2
    
25.                 s2.pop(0)
    
26.         else:
    
27.             if flg == 1:
    
28.                 if s3[0] == s2[0]:
    
29.                     s2.pop(0)
    
30.                     changed = True
    
31.                 elif s3[0] == s1[0]:
    
32.                     s1.pop(0)
    
33.                 else:
    
34.                     print('调试',3)
    
35.                     return False
    
36.             elif flg == 2:
    
37.                 if s3[0] == s1[0]:
    
38.                     s1.pop(0)
    
39.                     changed = True
    
40.                 elif s3[0] == s2[0]:
    
41.                     s2.pop(0)
    
42.                 else:
    
43.                     print('调试',3)
    
44.                     return False
    
45.         s3.pop(0)
    
46.     else:
    
47.         print('调试',4)
    
48.         return changed
    
49. 
    
50. if __name__ == '__main__':
    
51.     print('示例1 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"))
    
52.     print('示例2 输出：',solve(s1 = "", s2 = "", s3 = "1"))
    
53.     print('示例3 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
    
54.     print('之前错的',solve(s1 = "aa", s2 = "a", s3 = "aaa"))
    

复制代码

我之前在网上算了一挂，结果……
§ 大凶 §
诸事不宜
忌：玩网游
匹配到一群猪队友
忌：参加模拟赛
注意爆零
我之前还不信呢……现在……哈哈

zltzlt

阴阳神万物主 发表于 2019-11-2 13:21
这回，也许、大概没问题了
我之前在网上算了一挂，结果……
§ 大凶 §

zltzlt

阴阳神万物主 发表于 2019-11-2 13:21
这回，也许、大概没问题了
我之前在网上算了一挂，结果……
§ 大凶 §

解答错误

输入：s1 = "abbcddef", s2 = "accbbbcd", s3 = "abbcddefaccbbbcd"
打印：调试 4
输出：False
预期结果：True

122815306

zltzlt 发表于 2019-11-2 12:31
输入 s1 = '', s2 = '', s3 = '' 出错

啊 应该在最前面加上这两行
    if not (s1 and s2 and s3):
        return s3==s1+s2

danteer

1. course1 = 0
   
2. course2 = 0
   
3. course3 = 0
   
4. 
   
5. def str1check(s1,s3):
   
6.     global course1,course2,course3
   
7.     while course3 < len(s3) and course1 < len(s1):
   
8.         if s1[course1] == s3[course3]:
   
9.             course1 += 1
   
10.             course3 += 1
    
11.         else:
    
12.             break
    
13. 
    
14. def str2check(s2,s3):
    
15.     global course1,course2,course3
    
16.     while course3 < len(s3) and course2 < len(s2):
    
17.         if s2[course2] == s3[course3]:
    
18.             course2 += 1
    
19.             course3 += 1
    
20.         else:
    
21.             break
    
22.    
    
23. def func(s1,s2,s3):
    
24.     global course1,course2,course3
    
25.     while course3 != len(s3):
    
26.         temp = course3
    
27.         str1check(s1,s3)
    
28.         str2check(s2,s3)
    
29.         if temp == course3:
    
30.             return False
    
31.     if course1 == len(s1) and course2 == len(s2):
    
32.         return True
    
33.     else:
    
34.         return False

复制代码

阴阳神万物主

zltzlt 发表于 2019-11-2 13:25
解答错误

输入：s1 = "abbcddef", s2 = "accbbbcd", s3 = "abbcddefaccbbbcd"

兴许好使了

1. def differ(a:list,b:list):
   
2.     for i in range(min((len(a),len(b)))):
   
3.         if a[i] != b[i]:
   
4.             return i
   
5.     return min((len(a),len(b)))
   
6. def solve(s1:str,s2:str,s3:str)->bool:
   
7.     if len(s3) != len(s1+s2):
   
8.         #print('调试',1)
   
9.         return False
   
10.     elif not(len(s1)and len(s2)and len(s3)):
    
11.         #print('调试',5)
    
12.         return True
    
13.     a=set(s1+s2)
    
14.     for i in a:
    
15.         if s1.count(i) + s2.count(i) != s3.count(i):
    
16.             #print('调试',2)
    
17.             return False
    
18.     s1,s2,s3 = list(s1),list(s2),list(s3)
    
19.     begin = True
    
20.     num = differ(s1,s3)
    
21.     num1 = differ(s2,s3)
    
22.     if num > num1:
    
23.         flg = 2
    
24.     else:
    
25.         flg = 1
    
26.     while s1 and s2:
    
27.         if begin:
    
28.             begin = False
    
29.             if flg == 2:
    
30.                 #print('调试',s1[:num1],s2[:num1],s3[:num1])
    
31.                 s1 = s1[num1:]
    
32.                 s3 = s3[num1:]
    
33.             elif flg == 1:
    
34.                 #print('调试',s1[:num],s2[:num],s3[:num])
    
35.                 s2 = s2[num:]
    
36.                 s3 = s3[num:]
    
37.             #print('调试',s1,s2,s3)
    
38.             changed = False
    
39.             continue
    
40.         else:
    
41.             if flg == 1:
    
42.                 if s3[0] == s2[0]:
    
43.                     s2.pop(0)
    
44.                     changed = True
    
45.                     flg = 2
    
46.                 elif s3[0] == s1[0]:
    
47.                     s1.pop(0)
    
48.                 else:
    
49.                     #print('调试',3)
    
50.                     return False
    
51.             elif flg == 2:
    
52.                 if s3[0] == s1[0]:
    
53.                     s1.pop(0)
    
54.                     changed = True
    
55.                     flg = 1
    
56.                 elif s3[0] == s2[0]:
    
57.                     s2.pop(0)
    
58.                 else:
    
59.                     #print('调试',3)
    
60.                     return False
    
61.         s3.pop(0)
    
62.     else:
    
63.         #print('调试',4)
    
64.         return changed
    
65. 
    
66. if __name__ == '__main__':
    
67.     print('示例1 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"))
    
68.     print('示例2 输出：',solve(s1 = "", s2 = "", s3 = "1"))
    
69.     print('示例3 输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
    
70.     print('之前错的',solve(s1='aa',s2='a',s3='aaa'))
    
71.     print('之前错的',solve(s1 = "abbcddef", s2 = "accbbbcd", s3 = "abbcddefaccbbbcd"))
    

复制代码

zltzlt

阴阳神万物主 发表于 2019-11-2 17:07
兴许好使了

解答错误

输入：s1 = "aba", s2 = "a", s3 = "aaba"
输出：False
预期结果：True

阴阳神万物主

zltzlt 发表于 2019-11-2 13:25
解答错误

输入：s1 = "abbcddef", s2 = "accbbbcd", s3 = "abbcddefaccbbbcd"

嗯？这也算交叉？
s1 = "abbcddef", s2 = "accbbbcd", s3 = "abbcddefaccbbbcd"
这……拼接也算交叉啊？
我以为，至少这样算交叉呢：s3 = "abbcddeafccbbbcd"

阴阳神万物主

zltzlt 发表于 2019-11-2 17:59
解答错误

输入：s1 = "aba", s2 = "a", s3 = "aaba"

我这回又改了改，应该好使了：

1. def differ(a:list,b:list):
   
2.     for i in range(min((len(a),len(b)))):
   
3.         if a[i] != b[i]:
   
4.             return i
   
5.     return min((len(a),len(b)))
   
6. def solve(s1:str,s2:str,s3:str)->bool:
   
7.     if len(s3) != len(s1+s2):
   
8.         print('调试',1,'长度不对')
   
9.         return False
   
10.     elif (s3 == s1+s2)or(s3==s2+s1):
    
11.         print('调试',2,'算拼接')
    
12.         return True
    
13.     a=set(s1+s2)
    
14.     for i in a:
    
15.         if s1.count(i) + s2.count(i) != s3.count(i):
    
16.             print('调试',3,'数儿不对')
    
17.             return False
    
18.     s1,s2,s3 = list(s1),list(s2),list(s3)
    
19.     if s1[0] == s2[0]:
    
20.         num = differ(s1,s3)
    
21.         num1 = differ(s2,s3)
    
22.         if num == num1:
    
23.             if len(s1) >= len(s2):
    
24.                 flg = 1
    
25.             else:
    
26.                 flg = 2
    
27.         elif num > num1:
    
28.             flg = 1
    
29.         else:
    
30.             flg = 2
    
31.     elif s1[0] == s3[0]:
    
32.         flg = 1
    
33.     elif s2[0] == s3[0]:
    
34.         flg = 2
    
35.     if flg == 1:
    
36.         s1.pop(0)
    
37.     elif flg == 2:
    
38.         s2.pop(0)
    
39.     s3.pop(0)
    
40.     #print('调试',s1,s2,s3)
    
41.     changed = False
    
42.     while s1 or s2:
    
43.         if s1 == []:
    
44.             if s2[0] == s3[0]:
    
45.                 s2.pop(0)
    
46.             else:
    
47.                 print('调试',4,'顺序不对')
    
48.                 return False
    
49.         elif s2 == []:
    
50.             if s1[0] == s3[0]:
    
51.                 s1.pop(0)
    
52.             else:
    
53.                 print('调试',4,'顺序不对')
    
54.                 return False
    
55.         elif flg == 1:
    
56.             if s2[0] == s3[0]:
    
57.                 s2.pop(0)
    
58.                 if not changed:
    
59.                     changed = True
    
60.             elif s1[0] == s3[0]:
    
61.                 s1.pop(0)
    
62.             else:
    
63.                 print('调试',4,'顺序不对')
    
64.                 return False
    
65.         elif flg == 2:
    
66.             if s1[0] == s3[0]:
    
67.                 s1.pop(0)
    
68.                 if not changed:
    
69.                     changed = True
    
70.             elif s2[0] == s3[0]:
    
71.                 s2.pop(0)
    
72.             else:
    
73.                 print('调试',4,'顺序不对')
    
74.                 return False
    
75.         s3.pop(0)
    
76.     else:
    
77.         print('调试',5,'循环结束,能走到这儿，大概率是对的，但咱不赌')
    
78.         return changed
    
79. 
    
80. if __name__ == '__main__':
    
81.     print('示例1 T输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"))
    
82.     print('示例2 F输出：',solve(s1 = "", s2 = "", s3 = "1"))
    
83.     print('示例3 F输出：',solve(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
    
84.     print('之前错的T',solve(s1='aa',s2='a',s3='aaa'))
    
85.     print('之前错的T',solve(s1 = "abbcddef", s2 = "accbbbcd", s3 = "abbcddefaccbbbcd"))
    
86.     print('之前错的T',solve(s1 = "aba", s2 = "a", s3 = "aaba"))
    

复制代码

这回，要是再不对，我就……


这回要是再不好使，我就……


我就……


我就吃饭去！（嗯？你以为呢？）

zltzlt

阴阳神万物主 发表于 2019-11-2 19:11
我这回又改了改，应该好使了：

这回，要是再不对，我就……

还没吃饭吶