判断子序列

[编程题]判断子序列

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

给定两个字符串 S 和 T ，判断 S 是否是 T 的子序列。

即是否可以从 T 删除一些字符转换成 S。

数据范围： $1 \le len(S) \le 100 \$ ， $1 \le len(T) \le 10^4 \$ ，保证字符串中仅含有小写字母

示例1

输入

"nowcoder","nowcoder"

输出

true

示例2

输入

"nower","nowcoder"

输出

true

示例3

输入

"nowef","nowcoder"

输出

false

算法知识视频讲解

Python3

牛客633339748号

class Solution:

def isSubsequence(self , S: str, T: str) -> bool:

# write code here

n = len(S)

m = len(T)

dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1,n+1):

for j in range(1,m+1):

if S[i-1] == T[j-1]:

dp[i][j] = dp[i-1][j-1]+1

else:

dp[i][j] = dp[i][j-1]

return dp[-1][-1] == n

发表于今天 10:32:38 回复(0)

Python3

琵琶语

'''
这道题要不是在leetcode看过, 就没遇见出题人这么**, 都不好好出题或者直接从别的地方照搬。条件加上不改变相对位置。
思路：
1. 首先判断子串S的长度是否大于原串T的长度,若是则无法匹配,直接返回False。
2. 定义一个变量match_s表示匹配到的字符,一个变量ind_S表示子串S的当前索引。然后遍历原串T中的每一个字符,如果该字符与子串S当前索引指向的字符相同,则将该字符加入match_s中,并将ind_S加一。
3. 最后判断match_s是否等于子串S,若是则匹配成功,返回True,否则返回False。
'''
class Solution:
    def isSubsequence(self , S: str, T: str) -> bool:
        # write code here
        if len(S) > len(T):
            return False
        match_s = '' # 匹配到的字符
        ind_S = 0 # 子串S的索引
        for j in T:
            if j == S[ind_S]:
                match_s += j
                ind_S += 1
        if match_s == S:
            return True
        return False

编辑于 2023-03-28 11:05:30 回复(0)