LeetCode——交错字符串

NO.97 交错字符串困难

思路一：动态规划 还是常规的分析步骤

dp[i][j]的含义：s1的前i个元素和s2的前j个元素，是否可以交叉组成s3的前i+j个元素。

初始化：大小是[s1.length+1][s2.length+1]包含两个空串；dp[0][0]=true，即两个空串可以组成空串；第一行和第一列需要进行初始化，分别表示一个s1或s2为空串的情况下，是否可以只用另一个串即可组成s3。

状态转移：dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1) || dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1)，这个式子看着长其实很好理解，主要是在s3的当前元素之前都可以成功交叉组合的基础上，判断s1的i元素或者s2的j元素可以匹配s3的当前元素即为true。

public boolean isInterleave(String s1, String s2, String s3) {
    int m = s1.length(), n = s2.length();
    if (m + n != s3.length()) return false;
    //初始化
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0][0] = true;
    //s2为空串
    for (int i = 1; i < m + 1; i++) {
        dp[i][0] = dp[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1);
    }
    //s1为空串
    for (int j = 1; j < n + 1; j++) {
        dp[0][j] = dp[0][j - 1] && s2.charAt(j - 1) == s3.charAt(j - 1);
    }
    //状态转移
    for (int i = 1; i < m + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            dp[i][j] = (dp[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1))
                || (dp[i][j - 1] && s2.charAt(j - 1) == s3.charAt(i + j - 1));
        }
    }
    return dp[m][n];
}

时间复杂度：O(mn)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.97 交错字符串 困难

NO.97 交错字符串困难