算法系列--两个数组的dp问题(2)(上)

简介: 算法系列--两个数组的dp问题(2)

💕"往前走"💕

作者:Mylvzi

文章主要内容:算法系列–两个数组的dp问题(2)

大家好,今天为大家带来的是算法系列--两个数组的dp问题(2),今天的题目相较于(1)简单很多

1.交错字符串

链接:

https://leetcode.cn/problems/interleaving-string/description/

分析:

本题看起来和之前做过的题目有所不同,这里一共有三个字符串,但是实际上只有两个字符串,当s1字符串的位置和s2字符串的位置固定之后,s3也就固定了,所以我们只需研究s1,s2这两个字符串即可

  • 状态表示:两个子串这样的问题最常用的状态表示就是s1在[0,i]区间内xxxx,s2[0,j]区间内xxxx,本题也是.
    dp[i][j] : s1在[0,i]区间内的字符串和s2在[0,j]区间内的字符串能否拼接成s3
  • 状态转移方程的推导:往往是根据最后一个位置的状态划分,分析如下:
  1. s1[i] != s3[i + j] && s2[j] != s3[i + j],则根本无法拼接成s3–>false
  2. s1[i] == s3[i + j] || s2[j] == s3[i + j],只要其中有一个等于s3[i + j]就有可能拼接成s3,此时需要判断的是前一个位置能否拼接成s3,前一个位置成立,当前位置也成立;前一个位置不成立,当前位置也无法成立
  • 初始化:还是根据状态表示去进行初始化
    第一行:表示s1为空,则s1和s2要想拼接成s3,必须保证s2和s3完全相同
    第一列:表示s2为空,则s1和s2要想拼接成s3,必须保证s1和s3完全相同

    代码:
class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int m = s1.length(), n = s2.length();
        if(m + n != s3.length()) return false;
        s1 = " " + s1; s2 = " " + s2; s3 = " " + s3;
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;// 初始化第一个位置
        for(int j = 1; j <= n; j++) {// 初始化第一行
            if(s2.charAt(j) == s3.charAt(j)) dp[0][j] = true;
            else break;
        }
        for(int i = 1; i <= m; i++) {// 初始化第一列
            if(s1.charAt(i) == s3.charAt(i)) dp[i][0] = true;
            else break;
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = (s1.charAt(i) == s3.charAt(i + j) && dp[i - 1][j]) 
                        || (s2.charAt(j) == s3.charAt(i + j) && dp[i][j - 1]);
            }
        }
        return dp[m][n];// 返回值
    }
}

算法系列--两个数组的dp问题(2)(下)https://developer.aliyun.com/article/1480833?spm=a2c6h.13148508.setting.17.361f4f0eyTL4lb



目录
相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
43 0
|
4月前
|
算法 测试技术
【算法】二分算法——寻找旋转排序数组中的最小值
【算法】二分算法——寻找旋转排序数组中的最小值
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
48 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
27 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
158 0
|
2月前
|
算法 C++
【算法】DP背包问题(C/C++)
【算法】DP背包问题(C/C++)
|
2月前
|
人工智能 算法 BI
【算法】 线性DP(C/C++)
【算法】 线性DP(C/C++)
|
4月前
|
存储 算法 Java
深入算法基础二分查找数组
文章深入学习了二分查找算法的基础,通过实战例子详细解释了算法的逻辑流程,强调了确定合法搜索边界的重要性,并提供了Java语言的代码实现。
深入算法基础二分查找数组
|
4月前
|
算法
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
【Azure Developer】完成算法第4版书中,第一节基础编码中的数组函数 histogrm()
|
4月前
|
算法
【算法】模拟算法——外观数组(medium)
【算法】模拟算法——外观数组(medium)