0097._Interleaving_String.md

97. Interleaving String

难度:Hard

刷题内容

原题连接

• https://leetcode.com/problems/interleaving-string/

内容描述

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

思路 - 时间复杂度: O(N^2)- 空间复杂度: O(N^2)******

一般用暴力的方法去解这题，时间复杂度为O(2^n)，时间复杂度为指数级，肯定超时。因此我们可以用动态规划将时间复杂度优化到O(n^2)。解动态规划的关键就是找到状态转移方程，定义二维数组 dp[i][j]，表示 s1[i]和 s2[j]之后的子串是否能组成s3[i + j]。这样我们就能写出状态转移方程， dp[i][j] = (s1[i] == s3[i + j] && dp[i + 1][j]) || (s2[j] == s3[i + j] && dp[i][j + 1])

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int l1 = s1.length(),l2 = s2.length(),l3 = s3.length();
        if(l1 + l2 != s3.length())
            return 0;
        int dp[l1 + 2][l2 + 2];
        memset(dp,0,sizeof(dp));
        dp[l1][l2] = 1;
        for(int i = l1;i >= 0;--i)
            for(int j = l2;j >= 0;--j)
            {
                if(i < l1 && s1[i] == s3[i + j] && dp[i + 1][j])
                    dp[i][j] = 1;
                if(j < l2 && s2[j] == s3[i + j] && dp[i][j + 1])
                    dp[i][j] = 1;
            }
        return dp[0][0];
    }
};