代码随线录刷题|LeetCode 392.判断子序列 115.不同的子序列

简介: 代码随线录刷题|LeetCode 392.判断子序列 115.不同的子序列

392.判断子序列

题目链接:力扣

思路


比较简单的思路就是使用双指针来判断子序列,这里主要使用动态规划,是编辑距离的入门题目


1、确定dp数组

       dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]


2、确定递推公式

有两种情况:


175ab5f7c6d947a3b8406c0d50eaeea2.png


if (s[i - 1] == t[j - 1])

t中找到了一个字符在s中也出现了。dp[i][j] = dp[i - 1][j - 1] + 1;,因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]的基础上加1


if (s[i - 1] != t[j - 1])

此时相当于t要删除元素,t如果把当前元素t[j - 1]删除,那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了,即:dp[i][j] = dp[i][j - 1];


01ac404afdee490b886b94258fda60d0.png


动态动画推导视频推荐:判断子序列


3、初始化dp数组

       从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],所以dp[0][0]和dp[i][0]是一定要初始化的


ce1e943272714f29a06c18bb12db544b.png


4、遍历顺序

       从前向后进行遍历  


判断子序列

动态规划

class Solution {
    public boolean isSubsequence(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        // 创建dp数组
        int[][] dp = new int[slen+1][tlen+1];
        // 推导dp数组
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= tlen; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        // 获取结果
        if (dp[slen][tlen] == slen) {
            return true;
        } else {
            return false;
        }
    }
}

双指针

class Solution {
    public boolean isSubsequence(String s, String t) {
        int sindex = 0;
        int tindex = 0;
        while (sindex < s.length() && tindex < t.length()) {
            if (s.charAt(sindex) == t.charAt(tindex)) {
                sindex++;
            }
            tindex++;
        }
        return sindex == s.length();
    }
}

115.不同的子序列

题目链接:力扣

思路

反正不是很好理解,再多看几次吧

1、确定dp数组

dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]


2、确定递推公式

有两种情况:


s[i - 1] 与 t[j - 1]相等

当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成

dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]不相等时,dp[i][j]只有一部分组成

dp[i][j] = dp[i - 1][j]

3、初始化dp数组

       根据递推公式,要初始化dp[i][0] 和 dp[0][j],以及特殊的dp[0][0]


dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数,所以都是1


dp[0][j] 表示:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数,所以都是0


dp[0][0] 应该是1,空字符串s,可以删除0个元素,变成空字符串t


4、遍历顺序

       从上到下,从左到右

不同的子序列

class Solution {
    public int numDistinct(String s, String t) {
        int slen = s.length();
        int tlen = t.length();
        // 创建dp数组
        int[][] dp = new int[slen+1][tlen+1];
        // 初始化dp数组
        for (int i = 0; i < slen + 1; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= slen; i++) {
            for (int j = 1; j <= tlen; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; 
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[slen][tlen];
    }
}
相关文章
|
5天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
5天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
6天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
6天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
|
6天前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
|
6天前
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
【LeetCode刷题】专题三:二分查找模板
|
6天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
6天前
|
算法 容器
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
【LeetCode刷题】滑动窗口解决问题:水果成篮、找到字符串中所有字母异位词
|
6天前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
6天前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串