Interleaving String 29
Question
Given three strings: s1, s2, s3, determine whether s3 is formed by the interleaving of s1 and s2.
Example
For s1 = "aabcc", s2 = "dbbca"
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
Challenge
O(n2) time or better
Solution
dp[i][j]表示s1前i个和s2前j个对s3前i+j个是否interleaving string。
首先初始化。遍历s1,初始化所有的dp[i][0]
再遍历s2,初始化所有的dp[0][j]
若s3的第i+j-1位和s1的第i位相等,则看dp[i-1][j]是否为true;同理,若s3的i+j-1位和s2的第j位相等,则看dp[i][j-1]是否为true。只要两种情况中的任意一种为true,则dp[i][j]为true。
代码如下:
public class Solution {
/**
* Determine whether s3 is formed by interleaving of s1 and s2.
* @param s1, s2, s3: As description.
* @return: true or false.
*/
public boolean isInterleave(String s1, String s2, String s3) {
// write your code here
int n = s1.length();
int m = s2.length();
boolean[][] f = new boolean[n + 1][m + 1];
if(n + m != s3.length()){
return false;
}
f[0][0] = true;
for(int i = 1; i <= n; i++){
if(s3.charAt(i - 1) == s1.charAt(i - 1) && f[i - 1][0]){
f[i][0] = true;
}
}
for(int j = 1; j <= m; j++){
if(s3.charAt(j - 1) == s2.charAt(j - 1) && f[0][j - 1]){
f[0][j] = true;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(f[i - 1][j] && (s1.charAt(i - 1) == s3.charAt(i + j - 1)) || f[i][j - 1] && (s2.charAt(j - 1) == s3.charAt(i + j - 1))){
f[i][j] = true;
}
}
}
return f[n][m];
}
}