首页 > 试题广场 >

判断子序列

[编程题]判断子序列

热度指数：2821 时间限制：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

算法知识视频讲解

C++

QNBZ

class Solution {
public:
    bool isSubsequence(string S, string T) {
        vector<int>dp(S.size()+1);
        for(int i=1;i<=S.size();i++)
        {
            for(int j=i;j<=T.size();j++)
            {
                if(S[i-1]==T[j-1])
                    {dp[i]=max(dp[i],dp[i-1]+1);break;}
            }
        }
        if(dp[S.size()]==S.size())return true;
        return false;
    }
};

发表于 2022-01-05 16:07:50 回复(0)

Java

pein531

双指针

一个指针p₁指向S的首个字符，另一个指针p₂指向T的首个字符。如果字符相等，两个指针都移动；否则只移动p₂指针。直到遍历完某个字符串，如果p₁到了S的结尾，就说明S是T的子序列。时间复杂度为O(n)，其中n为T的长度。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    public boolean isSubsequence (String S, String T) {
        // write code here
        if(S.length() > T.length()) return false;
        int p1 = 0, p2 = 0;
        while(p1 < S.length() && p2 < T.length()){
            if(S.charAt(p1) == T.charAt(p2)){
                p1++;
                p2++;
            }else{
                p2++;
            }
        }
        if(p1 == S.length()) return true;
        return false;
    }
}

动态规划

检查S和T的最长公共子序列的长度是否为S.length()。时间复杂度O(m*n)，其中m为S的长度。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    bool isSubsequence(string S, string T) {
        // write code here
        int maxLen = 0;
        vector<vector<int>> dp(S.length() + 1, vector<int>(T.length() + 1));
        for(int i = 1; i <= S.length(); i++){
            for(int j = 1; j <= T.length(); j++){
                if(S[i - 1] == T[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                maxLen = maxLen > dp[i][j]? maxLen: dp[i][j];
            }
        }
        return maxLen == S.length();
    }
};

编辑于 2021-12-15 09:47:26 回复(0)

全栈工程师

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param S string字符串

* @param T string字符串

* @return bool布尔型

public boolean isSubsequence (String S, String T) {

// write code here

int[] s = new int[26];

int[] t = new int[26];

for (char c : S.toCharArray()) {

if (c >= 97 && c <= 122) {

s[c - 97]++;

}

for (char c : T.toCharArray()) {

if (c >= 97 && c <= 122) {

t[c - 97]++;

}

for (int i = 0; i < 26; i++) {

if (s[i] > t[i]) {

return false;

}

return true;

}

发表于 2023-07-04 21:36:54 回复(0)

Python 3

liangzhengjie

from operator import index
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串 
# @param T string字符串 
# @return bool布尔型
#
class Solution:
    def isSubsequence(self , S: str, T: str) -> bool:
        # write code here
        index = 0

        for s in T:
            if S[index] == s:
                index += 1
            
            if index == len(S):
                return True

        if index == len(S):
            return True
        return False

编辑于 2024-03-28 22:22:36 回复(0)

牛客2024007号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    public boolean isSubsequence (String S, String T) {
        // write code here
        // S是否是T的子序列
        // dp[i][j] S的 0 - i 是否是 T的 0 - j 的子序列
        boolean[][] dp = new boolean[S.length() + 1][T.length() + 1];
        dp[0][0] = true;
        for(int i = 0; i < T.length(); i++) {
            dp[0][i] = true;
        }
        for(int i = 1; i < S.length() + 1; i++) {
            for(int  j = 1; j < T.length() + 1; j++) {
                if(S.charAt(i - 1) == T.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i][j  - 1];
                }
            }
        }
        return dp[S.length()][T.length()];
    }
}

编辑于 2024-01-13 23:15:51 回复(0)

Rust

老刘001

struct Solution{

}

impl Solution {
    fn new() -> Self {
        Solution{}
    }

    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param S string字符串 
        * @param T string字符串 
        * @return bool布尔型
    */
    pub fn isSubsequence(&self, S: String, T: String) -> bool {
        // write code here
        self.check(&S[..], &T[..])
    }

    fn check(&self, s: &str, t: &str) -> bool {
        if s == "" && t == "" {return true}
        if s == "" {return false}
        if t == "" {return false}
        if s[0 ..= 0] == t[0 ..= 0] {
            self.check(&s[1 ..], &t[1 ..])
        } else {
            self.check(s, &t[1 ..])
        }
    }
}

发表于 2023-09-19 21:50:35 回复(0)

JavaScript Node

矜持的微笑

function isSubsequence( S , T ) {

// write code here

if(S.length===0)return true

let subI=0,i=0

while(i<T.length){

if(S[subI]===T[i]){

subI++

if(subI>=S.length)return true

}

i++

}

发表于 2023-06-24 08:03:14 回复(0)

牛客671537402号

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param S string字符串

* @param T string字符串

* @return bool布尔型

public boolean isSubsequence (String S, String T) {

// write code here

int j = 0;

for (int i = 0; i < T.length(); i++) {

if (T.charAt(i) == S.charAt(j)) {

j++;

}

return j == S.length();

}

极致的优雅,够短

发表于 2023-04-27 17:42:30 回复(0)

牛客565269855号

动态规划：
f[i][j]:S中前i个字符是否是T中前j个字符的子序列

 public boolean isSubsequence (String S, String T) {

        // write code here

        int len1 = S.length();

        int len2 = T.length();

        if(len1 > len2) return false;

        boolean[][] f = new boolean[len1 + 1][len2 + 1];

        for(int i=0;i<=len2;i++){

            f[0][i] = true; // 如果S为空，则一定是T的子串

        }

        // f[i][j]: S中前i个字符 是否是T中前j个字符的子序列

        // 递推：

        // 由于S中的每个字符都是要匹配的，而T中某些字符可以不需要，因此:

        // if S[i] == T[j], f[i][j] = f[i-1][j-1]

        // else f[i][j] = f[i][j-1] 即不用T[j]

        for(int i=1;i<=len1;i++){

            for(int j=1;j<=len2;j++){

                if(S.charAt(i-1) == T.charAt(j-1)){

                    f[i][j] |= f[i-1][j-1];

                }

                else{

                    f[i][j] = f[i][j-1];

                }

            }

        }

        return f[len1][len2];

    }

发表于 2023-04-01 15:58:47 回复(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)

小谷围做题家

package main
import _"fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param S string字符串 
 * @param T string字符串 
 * @return bool布尔型
*/
func isSubsequence( S string ,  T string ) bool {
    for _,ch:=range []byte(T){
        if len(S)==0{
            return true
        }
        if S[0]==ch{
            S=S[1:]
        }
    }
    if len(S)==0{
        return true
    }
    return false
}

发表于 2023-03-09 20:48:53 回复(0)

Java

牛客152482537号

import java.util.*;


public class Solution {
    /**
     * 
     * S字符先后顺序和T中一致
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return bool布尔型
     */
    public boolean isSubsequence (String S, String T) {
        // write code here
         if (S.equals(T) || T.contains(S)) return true;
        LinkedList<Character> linkedList = new LinkedList<>();
        //一次进入队列
        for (int i = 0; i < S.length(); i++) {
             linkedList.offer(S.charAt(i));
        }
        //遍历T
        for (int i = 0; i < T.length(); i++) {
             if (linkedList.isEmpty()) return true;
             //遇到相同字符弹出
             if (T.charAt(i) == linkedList.peek()) {
                 linkedList.poll();
             }
        }
        //最后判断队列是否为空
        return linkedList.isEmpty();
    }
}

发表于 2023-01-25 22:58:03 回复(0)

Python 3

牛客392113259号

class Solution:
def isSubsequence(self , S: str, T: str) -> bool:
# write code here
i, j = 0, 0
m, n = len(S), len(T)
while i < m and j < n:
if S[i] == T[j]:
i += 1
j += 1
else:
j += 1
if i == m:
return True
return False

发表于 2022-08-16 14:33:38 回复(0)

Java

牛客949377463号

public static boolean nc228(String s, String t) {
        boolean[][] dp = new boolean[s.length() + 1][t.length() + 1];
        Arrays.fill(dp[0], true);
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if(s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[s.length()][t.length()];
    }

发表于 2022-07-01 10:33:59 回复(0)

Java

人生太秃然


	public boolean isSubsequence (String S, String T) {
		// write code here
		if(T.indexOf(S) != -1) {
			return true;
		}
		char[] arr = S.toCharArray();
		char[] brr = T.toCharArray();
		int temp = 0;
		boolean flag = false;
		for (int i = 0; i < arr.length; i++) {
			for (int j = temp; j < brr.length; j++) {
				if (arr[i] == brr[j]) {
					System.out.println(j);
					flag = true;
					temp ++;
					break;
				} else {
					flag = false;
				}
			}
		}
		return flag;
	}

编辑于 2022-06-07 22:13:08 回复(0)

Java

半个西瓜半个夏

public boolean isSubsequence(String S, String T) {
        // write code here
        int i = 0, j = 0;
        int count = 0;
        while (i < S.length() && j < T.length()) {
            if (S.charAt(i) == T.charAt(j++)) {
                count++;
                i++;
            }
        }
        return count == S.length();
    }

发表于 2022-06-06 15:00:05 回复(0)

饥饿的懒羊羊在刷题

//动态规划思想

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @param T string字符串
* @return bool布尔型
*/
public boolean isSubsequence (String S, String T) {
// write code here
int row=S.length(),col=T.length();
int [][]dp=new int[row+1][col+1];
for(int i=1;i<=row;i++){
for(int j=1;j<=col;j++){
if(S.charAt(i-1)==T.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[row][col]==row;

}
}

发表于 2022-05-07 20:44:09 回复(0)

Python 3

闵小

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S string字符串
# @param T string字符串
# @return bool布尔型
#
class Solution:
    def isSubsequence(self , S: str, T: str) -> bool:
        # write code here
        import re
        pattern = ""
        for ch in S:
            pattern += ch + "[a-z]*"
        if re.search(pattern, T) == None:
            return False
        return True

发表于 2022-03-19 01:23:12 回复(0)

Python

温薬

    def isSubsequence(self , S , T ):
        # write code here
        ti=0
        si=0
        if len(S)>len(T):
            return False
        while ti<len(T) and si<len(S):
            if T[ti]==S[si]:
                if si==len(S)-1:
                    return True
                ti+=1
                si+=1
            else:
                ti+=1
        return False
#想用正则的因为记得有一个在每个字符后面插符号的函数的，结果尴尬的想不起来，算了，循环就循环吧

发表于 2021-11-29 22:19:41 回复(0)

提交观点

问题信息

动态规划字符串双指针

难度：

19条回答 36收藏 3596浏览

通过挑战的用户

查看代码

lucky

2023-03-08 19:14:26
牛客72914...

2022-09-15 06:36:06
Asphyxiay

2022-09-14 01:13:00
c语言大师

2022-09-12 17:12:53
四季豆&...

2022-09-11 23:33:37

判断子序列

输入

输出

输入

输出

输入

输出

双指针

动态规划

问题信息

热门推荐

通过挑战的用户

相关试题