Posted on 2014-01-20 21:12
Uriel 阅读(139)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
问string s3是否可由string s1和s2拼成(字母可以穿插)
sample：
s1 = "aabcc",s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
DP即可，dp[i][j]表示已匹配s3前i个字符，其中j个字符来自于s1
1 class Solution {
2 public:
3 int dp[1010][1010];
4
5 bool isInterleave(string s1, string s2, string s3) {
6 if(!s1.length()) return s2 == s3;
7 if(!s2.length()) return s1 == s3;
8 int len = s3.length();
9 if(len != s1.length() + s2.length()) return false;
10 memset(dp, 0, sizeof(dp));
11 dp[0][0] = 1;
12 for(int i = 1; i <= len; ++i) {
13 for(int j = 0; j <= i && j <= s1.length(); ++j) {
14 if(j >= 1 && s1[j - 1] == s3[i - 1] && dp[i - 1][j - 1]) {
15 dp[i][j] = 1;
16 }
17 else if(j >= 0 && j < i && (i - j - 1) < s2.length() && s2[i - j - 1] == s3[i - 1] && dp[i - 1][j]) {
18 dp[i][j] = 1;
19 }
20 if(i == len && dp[i][j]) return true;
21 }
22 }
23 return false;
24 }
25 };