首页 > 代码库 > Leetcode | Interleaving String

Leetcode | Interleaving String

2024-07-04 05:23:49   222人阅读

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.

用回溯TLE，所以想用dp来做。

为了方便计算，从尾往前扫。dp[i][j]表示s3[i+j...n3-1]是不是s1[i...n1-1]和s2[j...n2-1]的interleaving。

如果s3[i+j]=s1[i]，那么s[i+j...n3-1]是不是interleaving，取决于s1[i+1...n1-1]和s2[j...n2-1]是不是合法的interleaving。

如果s[i+1]=s2[j]，同理，取决于取决于s1[i...n1-1]和s2[j+1...n2-1]是不是合法的interleaving。

以上只要有一种情况满足就可以了。

dp[i][j] = ((s3[i + j] == s1[i] && dp[i + 1][j]) || (s3[i + j] == s2[j] && dp[i][j + 1]));

关于初始值：

i=n1的时候，也就是s1=“”，空串和s2是不是一个合法的interleaving，s2后半段和s3后半段都相同的部分全部为true。j=n2同理。

当然也可以认为，dp[i][n2] = (s3[i + n2] == s1[i] && dp[i+1][n2]);dp[n1][i] = (s3[i + n1] == s2[i] && dp[n1][i + 1]);

 1 class Solution {
 2 public:
 3     bool isInterleave(string s1, string s2, string s3) {
 4        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
 5        if (n1 + n2 != n3) return false;
 6        
 7        vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false));
 8        dp[n1][n2] = true;
 9        for (int i = n1 - 1; i >= 0; --i) {
10            dp[i][n2] = (s3[i + n2] == s1[i] && dp[i+1][n2]);
11        }
12        for (int i = n2 - 1; i >= 0; --i) {
13            dp[n1][i] = (s3[i + n1] == s2[i] && dp[n1][i + 1]);
14        }
15         
16        for (int i = n1 - 1; i >= 0; --i) {
17            for (int j = n2 - 1; j >= 0; --j) {
18                dp[i][j] = ((s3[i + j] == s1[i] && dp[i + 1][j])
19                             || (s3[i + j] == s2[j] && dp[i][j + 1])); 
20            }
21        }
22        
23 
24        return dp[0][0];
25     }
26 };

因为只用到上一行当前位置和当前行后一个位置，所以二维dp可以再优化成一维。

 1 class Solution {
 2 public:
 3     bool isInterleave(string s1, string s2, string s3) {
 4        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
 5        if (n1 + n2 != n3) return false;
 6        
 7        vector<bool> dp(n2 + 1, false);
 8        dp[n2] = true;
 9 
10        for (int i = n2 - 1; i >= 0; --i) {
11            dp[i] = (s3[i + n1] == s2[i] && dp[i + 1]);
12        }
13         
14        for (int i = n1 - 1; i >= 0; --i) {
15            dp[n2] = (s3[i + n2] == s1[i] && dp[n2]);
16            for (int j = n2 - 1; j >= 0; --j) {
17                dp[j] = ((s3[i + j] == s1[i] && dp[j])
18                             || (s3[i + j] == s2[j] && dp[j + 1])); 
19            }
20        }
21        
22 
23        return dp[0];
24     }
25 };

 

 


联系
我们