题目

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

For example,

Given: s1 = “aabcc”, s2 = “dbbca”,

When s3 = “aadbbcbcac”, return true.

When s3 = “aadbbbaccc”, return false.

思路

设dp[i][j]，表示s1[0,i-1]和s2[0,j-1]交替组成s3[0, i+j-1]。

如果s1[i-1]等于s3[i+j-1]，则dp[i][j]=dp[i-1][j]； 如果s2[j-1]等于s3[i+j-1]，则dp[i][j]=dp[i][j-1]。

因此状态转移方程如下：

dp[i][j] = dp[i-1][j] && (s1[i-1] == s3[i+j-1]) || dp[i][j-1] && (s2[j-1] == s3[i+j-1])

代码

/*------------------------------------------------*   日期：2015-03-25*   作者：SJF0115*   题目: 97.Interleaving String*   来源：https://leetcode.com/problems/interleaving-string/*   结果：AC*   来源：LeetCode*   博客：------------------------------------------------------*/#include 
     
      #include 
      
       using namespace std;class Solution {public:    bool isInterleave(string s1, string s2, string s3) {        int size1 = s1.size();        int size2 = s2.size();        int size3 = s3.size();        if(size1 + size2 < size3){            return false;        }//if        vector
       
        
          > dp(size1 + 1,vector
         
          (size2 + 1, false));        dp[0][0] = true;        // 初始化        for(int i = 1;i <= size1;++i){            dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1]);        }//for        for(int i = 1;i <= size2;++i){            dp[0][i] = dp[0][i-1] && (s2[i-1] == s3[i-1]);        }//for        for(int i = 1;i <= size1;++i){            for(int j = 1;j <= size2;++j){                dp[i][j] = dp[i-1][j] && (s1[i-1] == s3[i+j-1]) ||                    dp[i][j-1] && (s2[j-1] == s3[i+j-1]);            }//for        }//for        return dp[size1][size2];    }};int main() {    Solution solution;    string str1("aabcc");    string str2("dbbca");    string str3("aadbbbaccc");    cout<
          
           <
          
         
        
       
      
     

运行时间