我曾试图解决这个问题,但最终放弃了。后来我找到了下面的解决方案,虽然我不明白这个解决方案是如何工作的,也不知道为什么会有效。如果有更深入的解释,将不胜感激。
问题:
解决方案:Given
s1
,s2
,s3
, find whethers3
is formed by the interleaving ofs1
ands2
.For example, Given:
s1 = "aabcc" s2 = "dbbca"
- When
s3 = "aadbbcbcac"
, return true.- When
s3 = "aadbbbaccc"
, return false.
public static boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() == 0 && s1.length() == 0 && s2.length() == 0)
return true;
else if (s3.length() != s1.length() + s2.length())
return false;
boolean isInter[][] = new boolean[s1.length()+1][s2.length()+1];
isInter[0][0] = true;
for ( int i = 1; i <= s1.length(); ++i){
if (s1.charAt(i-1) == s3.charAt(i-1))
isInter[i][0] = true;
else
break;
}
for ( int i = 1; i <= s2.length(); ++i){
if (s2.charAt(i-1) == s3.charAt(i-1))
isInter[0][i] = true;
else
break;
}
// DP
for ( int i = 1; i <= s1.length(); ++i){
for ( int j = 1; j <= s2.length(); ++j){
if (s3.charAt(i+j-1) == s1.charAt(i-1))
isInter[i][j] = isInter[i-1][j] || isInter[i][j];
if (s3.charAt(i+j-1) == s2.charAt(j-1))
isInter[i][j] = isInter[i][j-1] || isInter[i][j];
}
}
return isInter[s1.length()][s2.length()];
}
A[:n] = A.substring(0,n)
和A[:-1] = A.substring(0,A.length-1)
。我认为您遇到的主要问题是在概念层面上,因此伪代码应该足以帮助您理解。 - Niklas B.