请教一道leetcode的新题# JobHunting - 待字闺中
i*e
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);
}
};
怎么才能不超时？用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);
}
};
