392. Is Subsequence （子序列判断）

川长思鸟来 2022-07-14 05:27 152阅读 0赞

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, `"ace"` is a subsequence of `"abcde"` while `"aec"` is not).

Example 1:  
s = `"abc"`, t = `"ahbgdc"`

Return `true`.

Example 2:  
s = `"axc"`, t = `"ahbgdc"`

Return `false`.

Follow up:  
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

题目大意：判断 字符串s 是否由 字符串t中的某些字符 ，按照原始的相对顺序构成的。

解题思路：同时遍历s和t，如果字符不相同，则右移t中的遍历下标；如果字符相同，则同时右移s和t中的遍历下标。如果t遍历完，而s还没遍历完，则返回false，否则返回true。代码如下：（11ms，beats 83.94%）

public class Solution {
        public boolean isSubsequence(String s, String t) {
            char[] ss = s.toCharArray(), tt = t.toCharArray();
    		int i, j = 0;
    		for (i = 0; i < ss.length; i++) {
    			while (j < tt.length && tt[j] != ss[i])
    				j++;
    			if (j == tt.length)
    				return false;
    			j++;
    		}
    		return true;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-392. 判断子序列

目录题目思路动态规划题目来源 [392. 判断子序列][392.] 题目思路这道算是编辑距离的入门题目，因为从题意中我们也

女爷i/ 2024年03月24日 09:30/ 0 赞/ 99 阅读

相关 392.判断子序列

392.判断子序列题干分析解题思路 1. 确定dp数组（dp table）以及下标的含义 2. 确定递推公式 3.

小咪咪/ 2023年10月16日 17:50/ 0 赞/ 66 阅读

相关 392. 判断子序列（双指针）

392. 判断子序列题目解题思路代码题目给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含

港控/mmm°/ 2023年10月05日 12:06/ 0 赞/ 60 阅读

相关 leetcode 392. 判断子序列

原题很简单，设一个双指针，遍历一下即可。现在讨论一下：如果有大量输入的 S，称作S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子

水深无声/ 2023年07月03日 08:22/ 0 赞/ 19 阅读

相关 LeetCode 392. Is Subsequence (贪心)

题目意思：有两个字符串 s 和 t，t 比较长，要求从 t 删掉点字符能和 s 对等，如果ok的话返回true，不OK返回fasle ![watermark_type_Z

末蓝、/ 2023年05月30日 10:46/ 0 赞/ 4 阅读

相关 leetcode 392. 判断子序列(C++)

题目给定字符串 s 和 t ，判断 s 是否为 t 的子序列。你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而

痛定思痛。/ 2023年05月28日 11:18/ 0 赞/ 30 阅读

相关 392. 判断子序列

> 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。 > > 一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"a

今天药忘吃喽~/ 2022年10月16日 09:46/ 0 赞/ 175 阅读

相关 392. Is Subsequence （子序列判断）

Given a string s and a string t, check if s is subsequence of t. You may assume that th

川长思鸟来/ 2022年07月14日 05:27/ 0 赞/ 153 阅读

相关【LeetCode】392. 判断子序列

题目链接：[https://leetcode-cn.com/problems/is-subsequence/description/][https_leetcode-cn.co

清疚/ 2022年05月10日 15:10/ 0 赞/ 142 阅读

相关 LeetCode: 392. Is Subsequence 是否是子序列

试题： Given a string s and a string t, check if s is subsequence of t. You may assume t

ゝ一世哀愁。/ 2021年06月24日 16:10/ 0 赞/ 326 阅读