vlambda博客
学习文章列表

本周小白与各位分享一道动态规划解决的字符串问题。在之前，小白也分享过这类题目，感兴趣的小伙伴可以点击查看（）。一直觉得动态规划是一种比较难解的问题，于是就多刷刷呗，每次刷到一些典型题目就和各位小伙伴儿分享一下吧~

交错字符串

★

leetcode97 --- 交错字符串【困难】

”

1、解题思路

在开篇的时候，我们已经提到过这道题可以使用动态规划来解决，那么我们脑海里应该就开始回忆动态规划的三个基本元素了吧~让我们来一起回忆一下！

• 动态数组dp的定义：在此题中，我们涉及到了三个字符串，其中s1和s2是我们可以进行的选择，s3是我们的目标。所以我们的转态就可以从s1和s2中选择，我们在此处定义dp[i][j]，表示s3的前(i+j)个字符串是否可以由s1的前i个和s2的前j个字符构成。

• 转态转移方程：dp[i][j]的取值，可以分为两种情况进行讨论

• 将 s1的第 i个字符与 s3的第 (i+j)个字符进行匹配，如果匹配成功，还需要查看 s1的前 i-1个字符 s2的前 j个字符与 s3的前 (i+j-1)个字符匹配的结果，即 dp[i-1][j]，此时 dp[i][j] =s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j] 。
• 将 s2的第 j个字符与 s3的第 (i+j)个字符进行匹配，如果匹配成功，还需要查看 s1的前 i个字符 s2的前 j-1个字符与 s3的前 (i+j-1)个字符匹配的结果，即 dp[i][j-1]，此时 dp[i][j] =s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1] 。
• 综上所述，我们的状态转移方程就出来了： dp[i][j] = (s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j]) || (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1]);

• 初始化：根据上面的dp定义已经状态转移方程，我们可以知道最小的子事件应该是dp[0][0]，此时代表的是s1的前0个字符，与s2前0个字符，与s3的前0个字符的匹配结果，我们可以认为此时是匹配的，所以dp[0][0]=true

经过上面三个转态的分析，我们就可以得到下面的代码实现部分了~

2、代码实现

    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length();
        int len2 = s2.length();
        int len3 = s3.length();

        if((len1 + len2) != len3) return false;

        //dp[i][j]表示s3的前(i+j)个字符串可以由s1的前i个和s2的前j个字符构成
        boolean[][] dp = new boolean[len1+1][len2+1];

        dp[0][0] = true;
        for(int i = 1 ; i <= len1 ; i++){
            dp[i][0] = (s1.charAt(i-1) == s3.charAt(i-1)) && dp[i-1][0];
        }
        for(int j = 1 ; j <= len2 ; j++){
            dp[0][j] = (s2.charAt(j-1) == s3.charAt(j-1)) && dp[0][j-1];
        }

        for(int i = 1 ; i <= len1 ; i++){
            for(int j = 1 ; j <= len2 ; j++){
                //分别将s3的(i+j)个字符与s1的i字符匹配，或者与s2的j字符匹配
                dp[i][j] = (s1.charAt(i-1) == s3.charAt(i+j-1) && dp[i-1][j]) || (s2.charAt(j-1) == s3.charAt(i+j-1) && dp[i][j-1]);
            }
        }
        return dp[len1][len2];
    }