1 class Solution {
2 public:
3 bool isInterleave(
string s1,
string s2,
string s3) {
4 if(s3.size() != s1.size() +
s2.size())
5 return false;
6 //create indicator
7 vector<vector<
bool> > match(s1.size() +
1, vector<
bool>(s2.size() +
1,
false));
8 //initialization the first row and the first column
9 match[
0][
0] =
true;
10 for(
int l1 =
1; l1 <= s1.size(); ++
l1 ) {
11 char c1 = s1[l1 -
1];
12 char c3 = s3[l1 -
1];
13 if (c1 ==
c3) {
14 match[l1][
0] =
true;
15 }
else
16 break;
17 }
18 for(
int l2 =
1; l2 <= s2.size(); ++
l2 ) {
19 char c2 = s2[l2 -
1];
20 char c3 = s3[l2 -
1];
21 if (c2 ==
c3) {
22 match[
0][l2] =
true;
23 }
else
24 break;
25 }
26 //work through the rest of matrix using the formula
27 for(
int l1 =
1; l1 <= s1.size(); ++
l1 ) {
28 char c1 = s1[l1 -
1];
29 for(
int l2 =
1 ; l2 <= s2.size() ; ++
l2 ) {
30 char c2 = s2[l2 -
1];
31 int l3 = l1 +
l2;
32 char c3 = s3[l3 -
1];
33 if (c1 ==
c3) {
34 match[l1][l2] = match[l1 -
1][l2] ||
match[l1][l2];
35 }
36 if (c2 ==
c3) {
37 match[l1][l2] = match[l1][l2 -
1] ||
match[l1][l2];
38 }
39 }
40 }
41 //the last element is the result
42 return match[s1.size()][s2.size()];
43 }
44 };
转载于:https://www.cnblogs.com/tanghulu321/archive/2013/05/13/3074974.html
相关资源：数据结构—成绩单生成器
