请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

leetcode每日一题——392.判断子序列(面试经典150题)

2023-07-13

一、题目描述与要求

392. 判断子序列 - 力扣(LeetCode)

题目描述

给定字符串 s 和 t ,判断 s 是否为 t 的子序列

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

示例

示例1:

输入:s = "abc", t = "ahbgdc"
输出:true

示例2:

输入:s = "axc", t = "ahbgdc"
输出:false

提示

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。

二、解题思路

总的思路:

       先分析题目,题目要求我们对所给出的两个字符串进行判断,判断字符串s是否是字符串t的子序列。要判断是否是其子序列,很简单就是字符串s中的元素t中都有,但需要注意的是元素是需要按照相对顺序组合的。

       因此我们可以利用双指针的方法,为两个字符串依次设置一个指针用来遍历字符串,其中指向字符串s的指针i只有在找到t中也有其对应元素时才向后移动,否则不移动。由此可以看出,如果字符串s不是字符串t的子序列,那么i就无法把s遍历完,因此,只需要判断i是否等于s的长度即可判断其是否为t的子序列。而指向字符串t的指针j则是一直向后移动,直至遍历完成。

具体步骤:

①获取两个字符串的长度

②定义双指针

③利用双指针对两个数组依次进行遍历,当元素相等时i++

④判断i是否等于n


三、具体代码【C语言】

bool isSubsequence(char * s, char * t){
    int n = strlen(s), m = strlen(t);//分别获取两个字符串的长度
    int i = 0, j = 0;
    //以T字符串为参照对象,利用双指针遍历两个数组,获取s与t的相同元素数量,如若与n不相等,则代表不是子序列
    while (i < n && j < m) {
        if (s[i] == t[j]) {  //元素相等时,i向后移动
            i++;
        }
        j++;
    }
    return i == n;
}

相关阅读

手机版|MSIPO技术圈 皖ICP备19022944号-2

Copyright © 2024, msipo.com

返回顶部