Leetcode#97 Interleaving String

原题地址

转化为二维地图游走问题。

比如s1="abab",s2="aab",s3="aabaabb",则有如下地图,其中"^"表示开始位置,"$"表示终止位置。

         a  a  b  <- s2
s1 -> a ^ . .
b . . .
a . . .
b . . $

现在问题变成了,能否走出一条等于s3的路径?

对于地图上的任意一点,不妨设坐标为(i, j),令k为当前坐标下s3对应的位置。

如果s1[i]=s3[k]则可以向下走

如果s2[j]=s3[k]则可以向右走

否则意味着无路可走了

令res[i][j]表示s1[i..s1.length-1]和s2[j..s2.length-1]能否组成s3[k..s3.length],其中s3.length-k=(s1.length-i) + (s2.length-j)

则有递推公式:res[i][j] = (s1[i]等于s3[k],且 res[i+1][j]) 或 (s2[j]等于s3[k],且res[i][j+1])

由于计算res[i][j]时只用到了res[i+1][j]或res[i][j+1](相邻层),所以在具体编码实现的时候可以进行状态压缩,用一维数组保存res[i][j]

代码:

 bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.length();
int len2 = s2.length();
int len3 = s3.length();
vector<bool> res(len2 + , false); if (len1 + len2 != len3) return false;
if (!len1) return s2 == s3;
if (!len2) return s1 == s3; res[len2] = true;
for (int j = len2 - ; j >= ; j--)
res[j] = s3[len3 - (len2 - j)] == s2[j] && res[j + ]; for (int i = len1 - ; i >= ; i--) {
for (int j = len2 - ; j >= ; j--) {
int k = len3 - (len1 - i) - (len2 - j);
res[j] = (s3[k] == s1[i] && res[j]) || (s3[k] == s2[j] && res[j + ]);
}
} return res[];
}
上一篇:Django基础(2)--模板自定义标签和过滤器,模板继承 (extend),Django的模型层-ORM简介


下一篇:Stimulsoft Reports筛选数据来绑定显示2个报表