392. Is Subsequence （子序列判断）

川长思鸟来 2022-07-14 05:27 135阅读 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 条评论，135人围观）

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

相关阅读

相关 LeetCode-392. 判断子序列

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

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

相关 392.判断子序列

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

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

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

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

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

相关 LeetCode动态规划子序列问题——392.判断子序列

题目描述： [392. 判断子序列![icon-default.png_t_M4AD][]https://leetcode.cn/problems/is-subseque

我不是女神ヾ/ 2023年09月28日 10:16/ 0 赞/ 99 阅读

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

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

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

相关 392. 判断子序列

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

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

相关 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 赞/ 136 阅读

相关 leetcode 392. Is Subsequence 子序列判断深度优先遍历DFS + 一个很简单的循环

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

傷城~/ 2022年06月04日 05:25/ 0 赞/ 163 阅读

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

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

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

相关 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 赞/ 306 阅读