i******e
发帖数: 273 | 1 interleaving string - 我用递归，judge small过了，judge large超时。
怎么才能不超时？用DP吗？如何定义最优子结构？ 谢谢！
class Solution {
public:
bool isInterleave(string s1, int start1, string s2, int start2, string
s3, int start3) {
bool isFirst = false;
bool isSecond = false;
if (start1 == s1.size() && start2 == s2.size() && start3 == s3.size(
))
return true;
if (start3 == s3.size() && (start1 < s1.size() || start2 < s2.size()
))
return false;
if (start3 < s3.size() && start1 == s1.size() && start2 == s2.size())
return false;
if (start3 < s3.length() && start1 < s1.size() && s1[start1] == s3[
start3])
isFirst = isInterleave(s1, start1 + 1, s2, start2, s3, start3 +
1);
if (start3 < s3.length() && start2 < s2.size() && s2[start2] == s3[
start3])
isSecond = isInterleave(s1, start1, s2, start2 + 1, s3, start3 +
1);
return isFirst || isSecond;
}
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return isInterleave(s1, 0, s2, 0, s3, 0);
}
}; | t****a
发帖数: 1212 | 2 http://www.mitbbs.com/article_t/JobHunting/32202217.html
size(
【在 i******e 的大作中提到】
: interleaving string - 我用递归，judge small过了，judge large超时。
: 怎么才能不超时？用DP吗？如何定义最优子结构？ 谢谢！
: class Solution {
: public:
: bool isInterleave(string s1, int start1, string s2, int start2, string
: s3, int start3) {
: bool isFirst = false;
: bool isSecond = false;
:
: if (start1 == s1.size() && start2 == s2.size() && start3 == s3.size(
| C***U
发帖数: 2406 | |
|
