论坛 › Python交流 › Python：每日一题 381

zltzlt 发表于 2020-4-20 17:44:44

Python：每日一题 381

今天的题目：

给定两个字符串 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

{:10_298:}欢迎大家一起答题！{:10_298:}

永恒的蓝色梦想 发表于 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

永恒的蓝色梦想 发表于 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)原文在这

kinkon 发表于 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 != s:
            j += 1
      elif s == t:
            i, j = i + 1, j + 1
      else:
            i += 1
    return i == r1 and j <= r2

March2615 发表于 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 == t:
            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.find(each)
      # m = l
      l = t.find(each, l + 1)
      if l == -1:
            return False
    return True
这里如果用切片，需要另一个量去记录，比较麻烦，可以直接用find实现

塔利班 发表于 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==t:
                index+=1
                break
            index+=1
    return True

永恒的蓝色梦想 发表于 2020-4-20 19:01:00

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


子序列必须按照顺序

永恒的蓝色梦想 发表于 2020-4-20 19:03:45

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

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

果然 C 写的就是牛逼{:10_266:}

kinkon 发表于 2020-4-20 19:23:26

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

是按顺序的啊

永恒的蓝色梦想 发表于 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++;
            }
      }
      return j==s.size();
    }
};

永恒的蓝色梦想 发表于 2020-4-20 19:24:14

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

Counter 不存在顺序这一说

kinkon 发表于 2020-4-20 19:33:16

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

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

liuzhengyuan 发表于 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 == t:
                t = t
                judge+=1
                break
    if judge == len(s):
      return True
    else:
      return False

March2615 发表于 2020-4-20 19:49:14

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

{:10_245:}我是用python写的啊，我不会C

lucky邪神 发表于 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,t,re.I|re.M)
      if flag ==None:
            return False
      
      newstart=flag.span()
      t=t
      if index==slen-1:
            return True

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

永恒的蓝色梦想 发表于 2020-4-20 20:03:13

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

我是说那个find……

ouyunfu 发表于 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:
            ls+=i
            break
          else:
            m+=1
    return True if ls==s else False

TJBEST 发表于 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)
    except:
      return False
    try:
      temp = t[::-1]
      end = len(t) - (temp.index(s[-1])+1)
    except:
      return False
    t = t
    if len(s) > len(t):
      return False
    M = len(s)
    N = len(t)
    Count =
    for i in range(0,M):
      try:
            temp = t.index(s)
      except:
            return False
      for j in range(temp,N):
            Count += 1
    temp = -1
    for i in range(0,M):
      tempChar = s
      while True:
            try:
                temp = t.index(tempChar,temp + 1)
            except:
                return False
            if Count > i:
                break
    return True

fan1993423 发表于 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
    if len(a)==len(set(a)):return True
    else:return False

Herry2020 发表于 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 == s:
                i += 1
                continue
            else:
                if i == 1:
                  t = t +t[(i+1):]
                else:
                  t = t[:i] + t[(i+1):]
      if t == s:
            return True
      else:
            return False
print(fun381(s, t))

查看完整版本: Python：每日一题 381