判断是不是子字符串

[编程题]判断是不是子字符串

热度指数：6531 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串 s和 t ，判断 s是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度n ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

输入描述:

共两行，第一行为字符串s,  第二行为字符串t
字符串t的长度 1<=n<=500000
字符串s的长度 1<=m<=100

输出描述:

输出true或者是false，true表示是s是t的子序列，false表示s不是t的子序列

示例1

输入

abc
ahbgdc

输出

true

示例2

输入

axc
ahbgdc

输出

false

算法知识视频讲解

Python 3

LHeaven

def s_isT(s, t):
    n = len(s)
    m = len(t)
    if n > m: 
        return 'false'
    p1 = p2 = 0
    res = ""
    while p1 < n and p2 < m:
        if s[p1] == t[p2]:
            res += s[p1]
            p1 += 1
            p2 += 1
        else:
            p2 += 1
    if res == s: 
        return 'true'
    else: 
        return 'false'
            
while True:
    try:
        s = input()
        t = input()
        print(s_isT(s, t))
    except:
        break

发表于 2021-08-30 14:57:46 回复(2)