[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* 博客：——————————————————*/;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;}//ifvector<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]);}//forfor(int i = 1;i <= size2;++i){dp[0][i] = dp[0][i-1] && (s2[i-1] == s3[i-1]);}//forfor(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}//forreturn 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;}

运行时间

联系朋友别欠费，天空辽阔任你飞，再多困难别后退! “