## Sunday, December 23, 2012

### [LeetCode] Interleaving String 解题报告

Given s1s2s3, 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.
» Solve this problem

[解题思路]

``````1:   bool isInterleave(string s1, string s2, string s3) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      if(s3.size() != (s1.size() + s2.size()))
5:      {
6:        return false;
7:      }
8:      int i =0, j= 0, k=0;
9:      while(i< s1.size() && j< s2.size())
10:      {
11:        if(s1[i] == s3[k])
12:        {
13:          i ++;
14:        }
15:        else if(s2[j] == s3[k])
16:        {
17:          j++;
18:        }
19:        else
20:        {
21:          return false;
22:        }
23:        k++;
24:      }
25:      while(i< s1.size())
26:      {
27:        if(s1[i] == s3[k])
28:        {
29:          i++;k++;
30:        }
31:        else
32:        {
33:          return false;
34:        }
35:      }
36:      while(j<s2.size())
37:      {
38:        if(s2[j] == s3[k])
39:        {
40:          j++;k++;
41:        }
42:        else
43:        {
44:          return false;
45:        }
46:      }
47:      return true;
48:    }
``````

s1 = a1, a2 ........a(i-1), ai
s2 = b1, b2, .......b(j-1), bj
s3 = c1, c3, .......c(i+j-1), c(i+j)

s1 = a1, a2 ........a(i-1)
s2 = b1, b2, .......b(j-1), bj
s3 = c1, c3, .......c(i+j-1)

```Match[i][j]
=   (s3.lastChar == s1.lastChar) && Match[i-1][j]
||(s3.lastChar == s2.lastChar) && Match[i][j-1]

i=0 && j=0时，Match[0][0] = true;
i=0时， s3[j] = s2[j], Match[0][j] |= Match[0][j-1]
s3[j] != s2[j], Match[0][j] = false;

j=0时， s3[i] = s1[i], Match[i][0] |= Match[i-1][0]
s3[i] != s1[i], Match[i][0] = false;
```

[Code]
``````1:    bool isInterleave(string s1, string s2, string s3) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      bool *matchUp = new bool[s2.size() +1];
5:      bool *matchDown = new bool[s2.size()+1];
6:      if(s3.size() != (s1.size() + s2.size())) return false;
7:      //initialize
8:      matchDown[0] = true;
9:      for(int i =1; i< s2.size() +1; i++)
10:      {
11:        if(s2[i-1] == s3[i-1])
12:          matchDown[i] |= matchDown[i-1];
13:        else
14:          matchDown[i]= false;
15:      }
16:      matchUp[0] = true;
17:      for(int i =1; i< s1.size() +1; i++)
18:      {
19:        if(s1[i-1] == s3[i-1])
20:          matchUp[0] |= matchDown[0];
21:        else
22:          matchUp[0]= false;
23:        for(int j =1;j<s2.size() +1; j++)
24:        {
25:          matchUp[j]=false;
26:          if(s1[i-1] == s3[i+j-1])
27:          {
28:            matchUp[j] |= matchDown[j];
29:          }
30:          if(s2[j-1] == s3[i+j-1])
31:          {
32:            matchUp[j] |= matchUp[j-1];
33:          }
34:        }
35:        bool* temp = matchUp;
36:        matchUp = matchDown;
37:        matchDown = temp;
38:      }
39:      return matchDown[s2.size()];
40:    }
``````

[总结]