[LeetCode]97.Interleaving String

题目

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 <iostream>
#include <vector>
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<vector<bool> > dp(size1 + 1,vector<bool>(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<<solution.isInterleave(str1,str2,str3)<<endl;
    return 0;
}

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>