g***j
发帖数: 1275 | 1 哪位大牛帮我看看这个代码，为什么leetcode online judge的small的都过了，large
的就过不了了？
test case 如下，说Time Limit Error, 是不是递归的算法太烂了？ 不至于这个都处
理不了吧？
"
bbbbbabbbbabaababaaaabbababbaaabbabbaaabaaaaababbbababbbbbabbbbababbabaababa
bbbaabababababbbaaababaa",
"
babaaaabbababbbabbbbaabaabbaabbbbaabaaabaababaaaabaaabbaaabaaaabaabaabbbbbbb
bbbbabaaabbababbabbabaab",
"
babbbabbbaaabbababbbbababaabbabaabaaabbbbabbbaaabbbaaaaabbbbaabbaaabababbaaa
aaabababbababaababbababbbababbbbaaaabaabbabbaaaaabbabbaaaabbbaabaaabaababaab
abbaaabbbbbabbbbaabbabaabbbbabaaabbababbabbabbab"
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!s1.length() && !s2.length() && !s3.length()) return true;
if(s3.length() != s1.length() + s2.length()) return false;
if(!s1.length()) return s2 == s3;
if(!s2.length()) return s1 == s3;
if(s3[0]!=s2[0] && s3[0]!= s1[0]) return false;
bool first = false;
bool second = false;
if(s3[0] == s1[0]) {
first = isInterleave(s1.substr(1,s1.length()-1), s2, s3.substr(1
, s3.length()-1));
if(first) return first;
}
if(s3[0] == s2[0]) {
second = isInterleave(s1, s2.substr(1,s2.length()-1), s3.substr(
1, s3.length()-1));
if(second) return second;
}
return false;
}
}; | l****c
发帖数: 782 | 2 记得是big的时候，得用DP吧，recursion太慢了。 | d*********g
发帖数: 154 | 3 练习一个：
public class Solution {
public boolean isInterleave(String s1, String s2, String s3)
{
if(s1 == null || s2 == null || s3 == null) return false;
if(s1.length() + s2.length() != s3.length()) return false;
boolean[][] matrix = new boolean[s1.length()+1][s2.length()+1];
matrix[0][0] = true;
for(int i = 1; i < matrix.length; ++i)
{
matrix[i][0] = (s3.charAt(i-1) == s1.charAt(i-1)) ? true :
false;
}
for(int i = 1; i < matrix[0].length; ++i)
{
matrix[0][i] = (s3.charAt(i-1) == s2.charAt(i-1)) ? true :
false;
}
for(int i = 1; i < matrix.length; ++i)
{
for(int j = 1; j < matrix[0].length; ++j)
{
if((matrix[i-1][j] == true && s1.charAt(i-1) == s3.charAt(
i+j-1)) || (matrix[i][j-1] == true && s2.charAt(j-1) == s3.charAt(i+j-1)))
{
matrix[i][j] = true;
}
else
{
matrix[i][j] = false;
}
}
}
return matrix[s1.length()][s2.length()];
}
} |
|
