本文共 1324 字，大约阅读时间需要 4 分钟。

题目概述

解题思路

动态规划。维护一个二维数组dp，dp[i][j]表示str1的前i个元素和str2的前j个元素恰好能够组成str3的前 i + j 的部分。这道题要求的值就是dp[len_str1][len_str2]，递归从矩阵左上角往右下角遍历。

先初始化二维数组的dp[i][0]和dp[0][j]两个部分，然后根据递推公式计算dp[i][j]：

方法性能

示例代码

class Solution {public:    bool isInterleave(string s1, string s2, string s3)     {        int len_s1 = s1.size(), len_s2 = s2.size(), len_s3 = s3.size();        if(len_s1 + len_s2 != len_s3)            return false;        else if(len_s1 == 0 && s2 == s3)            return true;        else if(len_s2 == 0 && s1 == s3)            return true;                int **dp = new int*[len_s1 + 1];        for(int i = 0 ; i < len_s1 + 1; ++i)            dp[i] = new int[len_s2 + 1];        dp[0][0] = 1;        for(int i = 1; i < len_s1 + 1; ++i)            dp[i][0] = (s1[i - 1] == s3[i - 1]) && dp[i - 1][0];        for(int j = 1; j < len_s2 + 1; ++j)            dp[0][j] = (s2[j - 1] == s3[j - 1]) && dp[0][j - 1];                for(int i = 1; i <= len_s1; ++i)        {            for(int j = 1; j <= len_s2; ++j)            {                if(dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1]))                    dp[i][j] = 1;                else if(dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1]))                    dp[i][j] = 1;                else                    dp[i][j] = 0;            }        }			return dp[len_s1][len_s2];    }};