97. Interleaving String
2016-06-29 本文已影响0人
HalcyonMoon
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.
设状态为 f[i][j]，表示 S3 的 0-(i+j+1)的子串是 S1 的 0-i 子串和 S2 的 0-j
子串的 interleaving string
则状态转移方程为：
f[i][j] = True f[i-1][j] && S1[i-1]==S3[i+j-1]
or f[i][j-1] && S2[j-1]==S3[i+j-1]
= False else
| null | d | b | b | c | a | |
|---|---|---|---|---|---|---|
| null | T | F | F | F | F | F |
| a | F | F | F | F | F | F |
| a | T | T | T | T | T | F |
| b | F | T | T | F | F | F |
| c | F | F | T | T | T | T |
| c | F | F | F | T | F | T |
s3 = "aadbbcbcac"
使用滚动数组优化空间复杂度
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int len1 = s1.length();
if(len1 == 0)
return s3.equals(s2);
int len2 = s2.length();
if(len2 == 0)
return s3.equals(s1);
if(len1 > len2){
return isInterleave(s2,s1,s3);
}
int len3 = s3.length();
if(len3 != len1+len2){
return false;
}
boolean [] f = new boolean[len2+1];
for(int i = 0; i<=len1; i++){
f[0] = (i==0 || f[0] && s1.charAt(i-1) == s3.charAt(i-1))?true:false;
for(int j = 1; j<=len2; j++){
f[j] = i != 0 && f[j] && s1.charAt(i-1) == s3.charAt(i+j-1) ||
f[j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
}
}
return f[len2];
}
}
