首页 > 试题广场 >

判断子序列

[编程题]判断子序列
  • 热度指数：3480 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串 S 和 T ，判断 S 是否是 T 的子序列。
即是否可以从 T 删除一些字符转换成 S。

数据范围： ， ，保证字符串中仅含有小写字母
示例1

输入

"nowcoder","nowcoder"

输出

true
示例2

输入

"nower","nowcoder"

输出

true
示例3

输入

"nowef","nowcoder"

输出

false
算法知识视频讲解
添加回答
C++
QNBZ头像 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)
全栈工程师头像 全栈工程师
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)
Java
pein531头像 pein531

双指针

一个指针p1指向S的首个字符，另一个指针p2指向T的首个字符。如果字符相等，两个指针都移动；否则只移动p2指针。直到遍历完某个字符串，如果p1到了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)
Python3
牛客633339748号头像 牛客633339748号
class Solution:
    def isSubsequence(self , S: str, T: str) -> bool:
        # write code here

        n = len(S)
        m = len(T)

        dp = [[0]*(m+1) for _ in range(n+1)]

        for i in range(1,n+1):
            for j in range(1,m+1):
                if S[i-1] == T[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = dp[i][j-1]
                   
        return dp[-1][-1] == n
发表于 2025-12-21 10:32:38 回复(0)
Java
明志_头像 明志_ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S string字符串
     * @param T string字符串
     * @return bool布尔型
     */
    public boolean isSubsequence (String S, String T) {
        int lenS = S.length();
        int lenT = T.length();

        int i = 0;
        int j = 0;
        while (i < lenS && j < lenT) {
            char chS = S.charAt(i);
            char chT = T.charAt(j);
            if (chS == chT) {
                i++;
                j++;
            } else {
                j++;
            }
        }
        if (i == lenS) {
            return true;
        }
        return false;
    }
}

发表于 2024-08-09 18:30:23 回复(0)
Python 3
liangzhengjie头像 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号头像 牛客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头像 老刘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号头像 牛客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号头像 牛客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)
Go
小谷围做题家头像 小谷围做题家 
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号头像 牛客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号头像 牛客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号头像 牛客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)
提交观点

问题信息

动态规划 字符串 双指针
难度：
21条回答 8638浏览

热门推荐

通过挑战的用户

查看代码

相关试题

判断子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号