k***g
发帖数: 166 | 1 网上都是2维DP的，我半年前用一个一维数组做出来了，现在却怎么也想不起来是什么
思路，上代码请教一下大家：
int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
if (n1 + n2 != n3) return false;
deque M(n2+1); M[n2] = true;
for (int j=n2-1; j>=0; j--)
if (!(M[j] = s3[n1+j] == s2[j] && M[j+1]))
break;
for (int i=n1-1; i>=0; i--) {
for (int j=n2-1; j>=0; j--) {
if ( s3[i+j] == s1[i] && M[j] )
M[j] = true;
else if ( s3[i+j] == s2[j] && M[j+1] )
M[j] = true;
else
M[j] = false;
}
M[n2] = s3[n2+i] == s1[i] && M[n2];
}
return M[0]; | M*******a
发帖数: 1633 | 2 recursion做的话什么辅助空间都不用把，除了stack space | M*******a
发帖数: 1633 | 3 recursion做的话什么辅助空间都不用把，除了stack space |
|
