第五十四天 | 动态规划 part15

392.判断子序列

题目链接/文字讲解：判断子序列

视频讲解：https://www.bilibili.com/video/BV1tv4y1B7ym

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

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

思路：简单题，懒得写思路了，直接上结果。不用动规更简单，动规为之后编辑距离做铺垫。

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        if (s.length() == 0) return true;
        if (t.length() == 0) return false;
        for (int j = 0; j < t.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
                if (i == s.length()) return true;
                continue;
            }
        }
        return false;
    }
}

115.不同的子序列

题目链接/文字讲解：不同的子序列

视频讲解：https://www.bilibili.com/video/BV1fG4y1m75Q

题设：给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

思路：难题，先过，等二刷。