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

zltzlt

今天的题目：

给定两个字符串 s 和 t，判断是否有可能删除 t 的若干个字符（也可以不删除）使得 s == t 。

注意：不能移动字符的位置。

示例 1：

输入：s = "133", t = "1133"
输出：True

示例 2：

输入：s = "abcde", t = "abcde"
输出：True

示例 3：

输入：s = "131", t = "1133"
输出：False

示例 4：

输入：s = "abc", t = "ahbgdc"
输出：True

示例 5：

输入：s = "axc", t = "ahbgdc"
输出：False

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

塔利班

2020-4-20 18:20:13

1. def f381(s,t):
   
2.     a=len(t)-len(s)
   
3.     index=0
   
4.     for i in range(len(s)):
   
5.         while 1:
   
6.             if a-index+i<0:
   
7.                 return False
   
8.             if s[i]==t[index]:
   
9.                 index+=1
   
10.                 break
    
11.             index+=1
    
12.     return True

复制代码

跳转到最佳答案楼层

永恒的蓝色梦想

利用迭代器实现的双指针

1. class Solution:
   
2.     def isSubsequence(self, s: str, t: str) -> bool:
   
3.         try:
   
4.             s=s.__iter__()
   
5.             last=s.__next__()
   
6. 
   
7.             for i in t:
   
8.                 if i==last:
   
9.                     last=s.__next__()
   
10. 
    
11.             return False
    
12.         
    
13.         except StopIteration:
    
14.             return True

复制代码

永恒的蓝色梦想

在力扣上发现一个很 NICE 的解法：

1. class Solution(object):
   
2.     def isSubsequence(self, s, t):
   
3.         t = iter(t)
   
4.         return all(c in t for c in s)

复制代码

原文在这

kinkon

双针不费空间

1. def f381(s, t):
   
2.     r1, r2 = len(s), len(t)
   
3.     i = j = 0
   
4.     while i < r1 and j < r2:
   
5.         if t[j] != s[i]:
   
6.             j += 1
   
7.         elif s[i] == t[j]:
   
8.             i, j = i + 1, j + 1
   
9.         else:
   
10.             i += 1
    
11.     return i == r1 and j <= r2

复制代码

March2615

1. def daily381(s: str, t: str) -> bool:
   
2.     # 解题思路：-> s是不是t的子序列
   
3.     # len(t) >= len(s)
   
4.     # 双指针，pt遍历t，ps遍历s，若pt==ps，ps+=1,same+=1
   
5.     if len(t) < len(s):
   
6.         return False
   
7.     pt, ps, same = 0, 0, 0
   
8.     while pt < len(t) and ps < len(s):
   
9.         if s[ps] == t[pt]:
   
10.             ps += 1
    
11.             same += 1
    
12.         pt += 1
    
13.     return same == len(s)

复制代码

想到昨天用find也很方便

1. def daily381(s: str, t: str) -> bool:
   
2.     l = -1  # find 找不到返回值为-1
   
3.     # m = 0
   
4.     for each in s:
   
5.         # l = t[m + l + 1:].find(each)
   
6.         # m = l
   
7.         l = t.find(each, l + 1)
   
8.         if l == -1:
   
9.             return False
   
10.     return True

复制代码

这里如果用切片，需要另一个量去记录，比较麻烦，可以直接用find实现

塔利班

1. def f381(s,t):
   
2.     a=len(t)-len(s)
   
3.     index=0
   
4.     for i in range(len(s)):
   
5.         while 1:
   
6.             if a-index+i<0:
   
7.                 return False
   
8.             if s[i]==t[index]:
   
9.                 index+=1
   
10.                 break
    
11.             index+=1
    
12.     return True

复制代码

永恒的蓝色梦想

kinkon 发表于 2020-4-20 18:01

子序列必须按照顺序

永恒的蓝色梦想

March2615 发表于 2020-4-20 18:16
想到昨天用find也很方便

这里如果用切片，需要另一个量去记录，比较麻烦，可以直接用find实现

果然 C 写的就是牛逼

kinkon

永恒的蓝色梦想 发表于 2020-4-20 19:01
子序列必须按照顺序

是按顺序的啊

永恒的蓝色梦想

1. const static auto _=[](){
   
2.     ios::sync_with_stdio(false);
   
3.     cin.tie(nullptr);
   
4.     cout.tie(nullptr);
   
5.     return NULL;
   
6. }();
   
7. 
   
8. 
   
9. class Solution {
   
10. public:
    
11.     bool isSubsequence(string s, string t) {
    
12.         int j=0;
    
13.         for(auto i:t){
    
14.             if(i==s[j]){
    
15.                 j++;
    
16.             }
    
17.         }
    
18.         return j==s.size();
    
19.     }
    
20. };

复制代码

永恒的蓝色梦想

kinkon 发表于 2020-4-20 19:23
是按顺序的啊

Counter 不存在顺序这一说

kinkon

永恒的蓝色梦想 发表于 2020-4-20 19:24
Counter 不存在顺序这一说

试出来了，是自动化问题，重复字符会按第一个排序

liuzhengyuan

（第一次来做题，有可能会错）
（这是一个很不错的方法）

1. def m381(s, t):
   
2.     i=0
   
3.     j=0
   
4.     judge=0
   
5.     for i in range(len(s)):
   
6.         for j in range(len(t)):
   
7.             if s[i] == t[j]:
   
8.                 t = t[j:]
   
9.                 judge+=1
   
10.                 break
    
11.     if judge == len(s):
    
12.         return True
    
13.     else:
    
14.         return False

复制代码

March2615

永恒的蓝色梦想 发表于 2020-4-20 19:03
果然 C 写的就是牛逼

我是用python写的啊，我不会C

lucky邪神

1. import re
   
2. 
   
3. def func381(s,t):
   
4.     slen=len(s)
   
5.     tlen=len(t)
   
6.     if slen >tlen:
   
7.         return False
   
8.     for index in range(slen):
   
9.         flag=re.search(s[index],t,re.I|re.M)
   
10.         if flag ==None:
    
11.             return False
    
12.         
    
13.         newstart=flag.span()[1]
    
14.         t=t[newstart:]
    
15.         if index==slen-1:
    
16.             return True
    
17. 
    
18. if __name__=='__main__':
    
19.     s=input("请输入一个待检测字符串：")
    
20.     t=input("请输入被检测字符串：")
    
21.     result=func381(s,t)
    
22.     print(result)

复制代码

永恒的蓝色梦想

March2615 发表于 2020-4-20 19:49
我是用python写的啊，我不会C

我是说那个find……

ouyunfu

1. 
   
2. def f381(s,t):
   
3.     m,n,ls=0,len(t),''
   
4.     for i in s:
   
5.         while m<n:
   
6.           if i==t[m]:
   
7.               ls+=i
   
8.               break
   
9.           else:
   
10.               m+=1
    
11.     return True if ls==s else False

复制代码

TJBEST

来个笨办法，可能超时

1. def fun381(s,t):
   
2.     if len(s) > len(t):
   
3.         return False
   
4.     try:
   
5.         start = t.index(s[0])
   
6.     except:
   
7.         return False
   
8.     try:
   
9.         temp = t[::-1]
   
10.         end = len(t) - (temp.index(s[-1])+1)
    
11.     except:
    
12.         return False
    
13.     t = t[start:(end+1)]
    
14.     if len(s) > len(t):
    
15.         return False
    
16.     M = len(s)
    
17.     N = len(t)
    
18.     Count = [0 for i in range(0,N)]
    
19.     for i in range(0,M):
    
20.         try:
    
21.             temp = t.index(s[i])
    
22.         except:
    
23.             return False
    
24.         for j in range(temp,N):
    
25.             Count[j] += 1
    
26.     temp = -1
    
27.     for i in range(0,M):
    
28.         tempChar = s[i]
    
29.         while True:
    
30.             try:
    
31.                 temp = t.index(tempChar,temp + 1)
    
32.             except:
    
33.                 return False
    
34.             if Count[temp] > i:
    
35.                 break
    
36.     return True

复制代码

fan1993423

1. def fun381(s,t):
   
2.     if set(s)&set(t)!=set(s):return False
   
3.     if s==t:return True
   
4.     a,b=[],0
   
5.     for i in s:
   
6.         a.append(t.find(i)+b)
   
7.         b+=t.find(i)+1
   
8.         t=t[t.find(i)+1:]
   
9.     if len(a)==len(set(a)):return True
   
10.     else:return False

复制代码

Herry2020

1. s = "abc"
   
2. t = "ahbgdc"
   
3. def fun381(s, t):
   
4.     if s == t:
   
5.         return True
   
6.     elif len(t) <= len(s):
   
7.         return False
   
8.     else:
   
9.         i = 0
   
10.         while len(t) > len(s):
    
11.             if t[i] == s[i]:
    
12.                 i += 1
    
13.                 continue
    
14.             else:
    
15.                 if i == 1:
    
16.                     t = t[0] +t[(i+1):]
    
17.                 else:
    
18.                     t = t[:i] + t[(i+1):]
    
19.         if t == s:
    
20.             return True
    
21.         else:
    
22.             return False
    
23. print(fun381(s, t))

复制代码