LeetCode刷题【392】判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

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

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

 

示例 1：

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

示例 2：

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

 

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

简单双指针解法 & 更新添加动态规划解法 & 一维DP数组

其实是想做dp来着。。。但是双指针看着太好理解了。写写个双指针

class Solution {
    public boolean isSubsequence(String s, String t) {
        int idxS = -1;
        int idxT = -1;
        while (++idxS < s.length() && idxT < t.length()){
            while (++idxT < t.length()){
                if (s.charAt(idxS) == t.charAt(idxT)){
                    break;
                }
            }
        }

        return idxS == s.length() && idxT < t.length();
    }
}

1. 在字符s和t上各一个指针
2. 从各自字符串起始位置开始，在t中找s上当前对应的字符，如果不是则t上的指针往后移动一位
3. 如果相同则s上之后往后移动一位，并t上的指针继续往后寻找当前s上的指向的字符
4. 最终如果s上的指针到结尾了，则表明是包含的

动态规划

在做了不少动态规划题目了，再看这个题目就非常简单了。
直接拿官方示例来举例子，自己画下这个矩阵就一下子一目了然、豁然开朗了。

如果还没看明白的话，我们把需要查找的子串换下再试试

状态转移方程

//如果当前字符相等
dp[row][col] = dp[rol-1][col-1]
//如果字符不等
dp[row][col] = dp[rol][col-1]

写份代码跑下试试吗，没毛病

class Solution {
    public boolean isSubsequence(String s, String t) {
        boolean[][] dp = new boolean[s.length()+1][t.length()+1];
        Arrays.fill(dp[0],true);
        int row = 0;
        while (++row<=s.length()){
            int col = 0;{
                while (++col<=t.length()){
                    dp[row][col] = s.charAt(row-1) == t.charAt(col-1)?dp[row-1][col-1]:dp[row][col-1];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

以及状态压缩一维DP数组，需要借一个`preStatus`记录前一位下标在更新前的值，也许还有其他更好的写法，暂时没想出来，可以留言多多交流

class Solution {
    public boolean isSubsequence(String s, String t) {
        boolean[] dp = new boolean[t.length()+1];
        Arrays.fill(dp,true);
        int sIdx = -1;
        boolean preStatus = true;
        while (++sIdx<s.length()){
            int tIdx = 0;
            dp[0] = false;
            preStatus = sIdx==0;
            while (++tIdx <= t.length()){
                boolean current = dp[tIdx];
                dp[tIdx] = s.charAt(sIdx)==t.charAt(tIdx-1)?preStatus:dp[tIdx-1];
                preStatus = current;
            }
        }
        return dp[t.length()];
    }
}