专栏首页Java那些事每天一道leetcode-392判断子序列

每天一道leetcode-392判断子序列

392_(判断子序列)Is Subsequence

1 问题描述、输入输出与样例

1.1 问题描述

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

后续挑战 : 如果有大量输入的 S,称作S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

1.2 输入与输出

输入:

  • string s:给定的字符串 s
  • string t:给定的字符串 t

输出:

  • bool:判断 s 是否为 t 的子序列

1.3 样例

1.3.1 样例1

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

1.3.2 样例2

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

2 思路描述与代码

2.1 思路描述(双下标法)

i为字符 s 的遍历下标, j 表示字符 t 的遍历下标

for( j = 0; j < len_t; j++ ){
    if(s[i] == t[j]){
        if(i == len_s - 1) return true;
        else i++;
    }
}

比如输入: s = "abc", t = "ahbgdc"; j = 0, i = 0, s[0] == t[0], i = 1; j = 1, i = 1, s[1] != t[1]; j = 2, i = 1, s[1] == t[2], i = 2; j = 3, i = 2, s[1] != t[3]; j = 4, i = 2, s[2] != t[4]; j = 5, i = 2, s[2] == t[5], 返回true;

2.2 代码

bool isSubsequence(string s, string t) {
    int len_s = s.size();
    int len_t = t.size();
    //边界情况
    if(len_s > len_t) return false;
    else if(len_s == 0) return true;

    //遍历t
    int i = 0, j = 0;
    for( j = 0; j < len_t; j++ ){
        //如果当前字符相等,查找 s 的下一个字符是否在 t 中
        if(s[i] == t[j]){
            if(i == len_s - 1) return true;
            else i++;
        }
    }
    return false;
}

3 思考与拓展

3.1 思考

本题按照子序列的定义并利用双下标法可以很容易解决。

3.1.1 其他方法

无。

3.1.2 复杂度分析

方法

空间复杂度

时间复杂度

双下标法

O(1)

O(s_len+t_len)

3.1.3 难点分析

  1. i下标的更新。

3.2 拓展

如果给你的是数组数据呢?

本文分享自微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每天一道leetcode151-反转字符串里的单词

    输入: "the sky is blue", 输出: "blue is sky the". 说明:

    乔戈里
  • 每天一道leetcode890-查找和替换模式

    你有一个单词列表 words 和一个模式 pattern,你想知道 words 中的哪些单词与模式匹配。

    乔戈里
  • 【leetcode】13:罗马数字转整数

    例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II ...

    乔戈里
  • 1347 旋转字符串

    1347 旋转字符串 基准时间限制:1 秒 空间限制:131072 KB 分值: 5 难度:1级算法题 S[0...n-1]是一个长度为n的字符串,定义旋转函数...

    Angel_Kitty
  • [剑指offer] 把数组排成最小的数

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

    尾尾部落
  • 小程序,公众号,App的微信支付详解

    honey缘木鱼
  • 不动程序的设计,不是好的用户体验师

    发现问题 前期做规范的过程是十分痛苦的,每做一个板块都要花很多时间去思考怎么表达、展示才能让其他设计师和程序员都一目了,然而随着内容的增加,发现很多地方无法深入...

    BestSDK
  • 仅需添加一行代码,即可让Pandas加速四倍 | Pandas on Ray

    如何让Pandas更快更省心呢?快来了解新库Modin,可以分割pandas的计算量,提高数据处理效率,一行代码即刻开启Pandas四倍速。

    昱良
  • 通过实例解析Python return运行原理

    程序运行到所遇到的第一个return即返回(退出def块),不会再运行第二个return。代码如下

    砸漏
  • 【GAMES101-现代计算机图形学课程笔记】Lecture 09 Shading 3 (纹理映射)

    这里补充一下上一节遗漏的一丢丢知识点,见下图。左边是渲染后的平面图,右边是对应的纹理。另外无论纹理平面原始有多大,最后都会被映射在

    marsggbo

扫码关注云+社区

领取腾讯云代金券