97. Interleaving String.md

97. Interleaving String

思路

仔细分析问题不难发现会涉及到大量子问题，所以我们考虑用动态规划求解。我们定义 dp[i][j] 表示 s1 的前 i 个元素和 s2 的前 j 个元素是否能交错组成 s3 的前 i + j 个元素。可得到初始状态和状态转移方程为：

初始态（即都为空串）：dp[0][0] = true
转移方程：dp[i][j] = (dp[i-1][j] && s3[i+j-1] == s1[i-1]) || (dp[i][j-1] && s3[i+j-1] == s2[j-1])

再考虑下边界条件就不难写出代码。另外由于 dp[i][j] 只和左上元素有关，故可以考虑使用滚动数组优化空间复杂度为O(s2.size())。

C++

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s1.size() + s2.size() != s3.size()) return false;
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if(n1 == 0) return s2 == s3;
        if(n2 == 0) return s1 == s3;
        
        // vector<vector<bool>>dp(n1 + 1, vector<bool>(n2 + 1, false));
        // for(int i = 0; i <= n1; i++){
        //     for(int j = 0; j <= n2; j++){
        //         if(i == 0 && j == 0) dp[i][j] = true;
        //         else if(i > 0 && dp[i-1][j] && s3[i+j-1] == s1[i-1]) dp[i][j] = true;
        //         else if(j > 0 && dp[i][j-1] && s3[i+j-1] == s2[j-1]) dp[i][j] = true;
        //         // else dp[i][j] = false; 
        //     }
        // }
        // return dp[n1][n2];

        // 滚动数组空间优化
        vector<bool>dp(n2 + 1, false);
        for(int i = 0; i <= n1; i++){
            for(int j = 0; j <= n2; j++){
                if(i == 0 && j == 0) dp[j] = true;
                else if(i > 0 && dp[j] && s3[i+j-1] == s1[i-1]) dp[j] = true;
                else if(j > 0 && dp[j-1] && s3[i+j-1] == s2[j-1]) dp[j] = true;
                else dp[j] = false; // 注意这里需重置成false, 因为dp[i-1][j]可能等于true
            }
        }
        return dp[n2];
    }
};