鱼C论坛

 找回密码
 立即注册
查看: 4252|回复: 66

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

[复制链接]
发表于 2020-4-20 17:44:44 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
今天的题目:


给定两个字符串 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
本帖最后由 塔利班 于 2020-4-20 18:26 编辑
def f381(s,t):
    a=len(t)-len(s)
    index=0
    for i in range(len(s)):
        while 1:
            if a-index+i<0:
                return False
            if s[i]==t[index]:
                index+=1
                break
            index+=1
    return True

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-4-20 17:48:24 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2020-4-20 17:55 编辑

利用迭代器实现的双指针
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        try:
            s=s.__iter__()
            last=s.__next__()

            for i in t:
                if i==last:
                    last=s.__next__()

            return False
        
        except StopIteration:
            return True

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 17:58:27 | 显示全部楼层
在力扣上发现一个很 NICE 的解法:
class Solution(object):
    def isSubsequence(self, s, t):
        t = iter(t)
        return all(c in t for c in s)
原文在这
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 18:01:25 | 显示全部楼层
本帖最后由 kinkon 于 2020-4-22 14:33 编辑

双针不费空间
def f381(s, t):
    r1, r2 = len(s), len(t)
    i = j = 0
    while i < r1 and j < r2:
        if t[j] != s[i]:
            j += 1
        elif s[i] == t[j]:
            i, j = i + 1, j + 1
        else:
            i += 1
    return i == r1 and j <= r2

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5 119 ms

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 18:16:43 | 显示全部楼层
本帖最后由 March2615 于 2020-4-20 18:53 编辑
def daily381(s: str, t: str) -> bool:
    # 解题思路:-> s是不是t的子序列
    # len(t) >= len(s)
    # 双指针,pt遍历t,ps遍历s,若pt==ps,ps+=1,same+=1
    if len(t) < len(s):
        return False
    pt, ps, same = 0, 0, 0
    while pt < len(t) and ps < len(s):
        if s[ps] == t[pt]:
            ps += 1
            same += 1
        pt += 1
    return same == len(s)

想到昨天用find也很方便
def daily381(s: str, t: str) -> bool:
    l = -1  # find 找不到返回值为-1
    # m = 0
    for each in s:
        # l = t[m + l + 1:].find(each)
        # m = l
        l = t.find(each, l + 1)
        if l == -1:
            return False
    return True
这里如果用切片,需要另一个量去记录,比较麻烦,可以直接用find实现

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 18:20:13 | 显示全部楼层    本楼为最佳答案   
本帖最后由 塔利班 于 2020-4-20 18:26 编辑
def f381(s,t):
    a=len(t)-len(s)
    index=0
    for i in range(len(s)):
        while 1:
            if a-index+i<0:
                return False
            if s[i]==t[index]:
                index+=1
                break
            index+=1
    return True

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 2 反对 0

使用道具 举报

发表于 2020-4-20 19:01:00 | 显示全部楼层

子序列必须按照顺序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:03:45 | 显示全部楼层
March2615 发表于 2020-4-20 18:16
想到昨天用find也很方便

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

果然 C 写的就是牛逼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:23:26 | 显示全部楼层

是按顺序的啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:23:28 | 显示全部楼层
const static auto _=[](){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    return NULL;
}();


class Solution {
public:
    bool isSubsequence(string s, string t) {
        int j=0;
        for(auto i:t){
            if(i==s[j]){
                j++;
            }
        }
        return j==s.size();
    }
};
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:24:14 | 显示全部楼层

Counter 不存在顺序这一说
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:33:16 | 显示全部楼层
永恒的蓝色梦想 发表于 2020-4-20 19:24
Counter 不存在顺序这一说

试出来了,是自动化问题,重复字符会按第一个排序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:40:10 | 显示全部楼层
本帖最后由 liuzhengyuan 于 2020-4-20 20:03 编辑

(第一次来做题,有可能会错)
(这是一个很不错的方法)
def m381(s, t):
    i=0
    j=0
    judge=0
    for i in range(len(s)):
        for j in range(len(t)):
            if s[i] == t[j]:
                t = t[j:]
                judge+=1
                break
    if judge == len(s):
        return True
    else:
        return False

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:49:14 | 显示全部楼层

我是用python写的啊,我不会C
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 19:55:03 | 显示全部楼层
import re

def func381(s,t):
    slen=len(s)
    tlen=len(t)
    if slen >tlen:
        return False
    for index in range(slen):
        flag=re.search(s[index],t,re.I|re.M)
        if flag ==None:
            return False
        
        newstart=flag.span()[1]
        t=t[newstart:]
        if index==slen-1:
            return True

if __name__=='__main__':
    s=input("请输入一个待检测字符串:")
    t=input("请输入被检测字符串:")
    result=func381(s,t)
    print(result)

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 20:03:13 | 显示全部楼层
March2615 发表于 2020-4-20 19:49
我是用python写的啊,我不会C

我是说那个find……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 20:23:33 | 显示全部楼层
def f381(s,t):
    m,n,ls=0,len(t),''
    for i in s:
        while m<n:
          if i==t[m]:
              ls+=i
              break
          else:
              m+=1
    return True if ls==s else False

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 20:35:05 | 显示全部楼层
本帖最后由 TJBEST 于 2020-4-21 17:47 编辑

来个笨办法,可能超时
def fun381(s,t):
    if len(s) > len(t):
        return False
    try:
        start = t.index(s[0])
    except:
        return False
    try:
        temp = t[::-1]
        end = len(t) - (temp.index(s[-1])+1)
    except:
        return False
    t = t[start:(end+1)]
    if len(s) > len(t):
        return False
    M = len(s)
    N = len(t)
    Count = [0 for i in range(0,N)]
    for i in range(0,M):
        try:
            temp = t.index(s[i])
        except:
            return False
        for j in range(temp,N):
            Count[j] += 1
    temp = -1
    for i in range(0,M):
        tempChar = s[i]
        while True:
            try:
                temp = t.index(tempChar,temp + 1)
            except:
                return False
            if Count[temp] > i:
                break
    return True

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 21:04:54 | 显示全部楼层
def fun381(s,t):
    if set(s)&set(t)!=set(s):return False
    if s==t:return True
    a,b=[],0
    for i in s:
        a.append(t.find(i)+b)
        b+=t.find(i)+1
        t=t[t.find(i)+1:]
    if len(a)==len(set(a)):return True
    else:return False

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-20 21:52:32 | 显示全部楼层
本帖最后由 zltzlt 于 2020-4-21 17:54 编辑
s = "abc"
t = "ahbgdc"
def fun381(s, t):
    if s == t:
        return True
    elif len(t) <= len(s):
        return False
    else:
        i = 0
        while len(t) > len(s):
            if t[i] == s[i]:
                i += 1
                continue
            else:
                if i == 1:
                    t = t[0] +t[(i+1):]
                else:
                    t = t[:i] + t[(i+1):]
        if t == s:
            return True
        else:
            return False
print(fun381(s, t))

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-20 22:45

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表