EEPW论坛

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.

1. class Solution  

2. {  

3. public:  

4.     bool isInterleve(string s1, string s2, string s3)  

5.     {  

6.         int rows = s1.length();  

7.         int cols = s2.length();  

8.         int lens = s3.length();  

9.   

10.         if ((rows+cols)!=lens)  

11.         {  

12.             return false;  

13.         }  

14.         if (rows==0 || cols==0)  

15.         {  

16.             if ((rows==0 && s2!=s3)  

17.                 || (cols==0 && s1!=s3))  

18.             {  

19.                 return false;  

20.             }  

21.         }  

22.   

23.         vector<vector<int>> dp(rows+1, vector<int>(cols+1, false));  

24.         dp[0][0] = true;  

25.           

26.        //初始化操作  

27.         for (int i=1; i<=rows; i++)  

28.         {  

29.             dp[i][0] = dp[i - 1][0] && (s1[i-1]==s3[i-1]);  

30.         }  

31.   

32.         for (int i = 1; i <= cols; i++)  

33.         {  

34.             dp[0][i] = dp[0][i] && (s2[i - 1] == s3[i - 1]);  

35.         }  

36.   

37.         for (int i=1; i<=rows; i++)  

38.         {  

39.             for (int j=1; j<=cols; j++)  

40.             {  

41.                 //要满足条件，则s3的最后一个要么是s1的最后一个字符  

42.                 //要么是s2的最后一个字符  

43.                 if (s3[i + j - 1] == s1[i - 1] && dp[i - 1][j])  

44.                 {  

45.                     dp[i][j] = true;  

46.                 }  

47.                 else if (s3[i + j - 1] == s2[j - 1] && dp[i][j - 1])  

48.                 {  

49.                     dp[i][j] = true;  

50.                 }  

51.                 else  

52.                     dp[i][j] = false;  

53.             }  

54.         }  

55.   

56.             return dp[rows][cols];  

57.     }  

58. };