C***U 发帖数: 2406 | 1 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
请牛人指点1 2 |
c********t 发帖数: 5706 | 2 给个原题吧
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法 : 请牛人指点1 2
|
C***U 发帖数: 2406 | 3 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给个原题吧
|
c*****a 发帖数: 808 | 4 呃。。刚刚写的, 过不了 Progress: 47/48 test cases passed.
大牛看看有啥bug
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
if (l1+l2 != l3) return false;
if (s1.equals("")) return s2.equals(s3);
if (s2.equals("")) return s1.equals(s3);
while(l3 >0 && l2 >0 && l1>0){
if(s3.charAt(l3-1) != s2.charAt(l2-1) && s3.charAt(l3-1) != s1.
charAt(l1-1))
return false;
else
if(s3.charAt(l3-1) == s2.charAt(l2-1)){
l3--;
l2--;
}
else
if(s3.charAt(l3-1) == s1.charAt(l1-1)){
l3--;
l1--;
}
}
return true;
}
} |
e******o 发帖数: 757 | 5 what if s1[i]=s2[i]=s3[i]
【在 c*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃。。刚刚写的, 过不了 Progress: 47/48 test cases passed. : 大牛看看有啥bug : public class Solution { : public boolean isInterleave(String s1, String s2, String s3) { : // Start typing your Java solution below : // DO NOT write main() function : int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); : if (l1+l2 != l3) return false; : if (s1.equals("")) return s2.equals(s3); : if (s2.equals("")) return s1.equals(s3);
|
C***U 发帖数: 2406 | 6 跑一下这个例子
s3: abaa
s1: aa
s2: ba
【在 c*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃。。刚刚写的, 过不了 Progress: 47/48 test cases passed. : 大牛看看有啥bug : public class Solution { : public boolean isInterleave(String s1, String s2, String s3) { : // Start typing your Java solution below : // DO NOT write main() function : int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); : if (l1+l2 != l3) return false; : if (s1.equals("")) return s2.equals(s3); : if (s2.equals("")) return s1.equals(s3);
|
l***i 发帖数: 1309 | 7 Mine is O(n^2) and passed, how do you do O(n) time? |
e******o 发帖数: 757 | 8 same here
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Mine is O(n^2) and passed, how do you do O(n) time?
|
c*****a 发帖数: 808 | 9 感谢阿,过了
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
if (l1+l2 != l3) return false;
if (s1.equals("")) return s2.equals(s3);
if (s2.equals("")) return s1.equals(s3);
if(s3.charAt(l3-1) != s2.charAt(l2-1) && s3.charAt(l3-1) != s1.
charAt(l1-1))
return false;
if(s3.charAt(l3-1) == s2.charAt(l2-1) && s3.charAt(l3-1) == s1.
charAt(l1-1)){
return isInterleave(s1, s2.substring(0, l2 - 1), s3.substring(0,
l3 - 1)) ||
isInterleave(s1.substring(0, l1-1), s2, s3.substring(0,
l3-1)) ;
}
if(s3.charAt(l3-1) == s2.charAt(l2-1))
return isInterleave(s1, s2.substring(0, l2 - 1), s3.substring(0,
l3 - 1));
if(s3.charAt(l3-1) == s1.charAt(l1-1))
return isInterleave(s1.substring(0, l1-1), s2, s3.substring(0,
l3-1)) ;
return true;
}
} |
C***U 发帖数: 2406 | 10 我这不是来询问的么。。。。呵呵
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Mine is O(n^2) and passed, how do you do O(n) time?
|
|
|
C***U 发帖数: 2406 | 11 我能想到的就是O(n^2)时间 O(n)空间的
bool isInterleaveNew(string s1, string s2, string s3) {
vector possibleIndex;
vector tempIndex;
if(s1.empty()) {
return s2 == s3;
}
if(s2.empty()) {
return s1 == s3;
}
if(s1.size() + s2.size() != s3.size()) {
return false;
}
if(s1[0] != s3[0] && s2[0] != s3[0]) {
return false;
}
else {
if(s2[0] == s3[0]) {
possibleIndex.push_back(-1);
}
if(s1[0] == s3[0]) {
possibleIndex.push_back(0);
}
}
for(int i = 1; i < s3.size(); i++) {
for(int j = 0; j < possibleIndex.size(); j++) {
int k = possibleIndex[j];
if(i - k - 1 < s2.size() && s2[i - k - 1] == s3[i] && (tempIndex
.empty() || (!tempIndex.empty() && tempIndex[tempIndex.size() - 1] != k))) {
tempIndex.push_back(k);
}
if(k + 1 < s1.size() && s1[k + 1] == s3[i]) {
tempIndex.push_back(k + 1);
}
}
possibleIndex = tempIndex;
tempIndex.clear();
if(possibleIndex.empty()) {
return false;
}
}
return true;
}
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Mine is O(n^2) and passed, how do you do O(n) time?
|
p*****2 发帖数: 21240 | |
a****a 发帖数: 15 | 13 s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac".
for( each char in s1) {
if(s3 has it) {
remove it
} else {
return false
}
}
return (s3==s2) |
c********t 发帖数: 5706 | 14 用backtracking + recursion是O(n)时间,O(1)空间吗?
我的48个case都过了,但是judge large超时了!
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法 : 请牛人指点1 2
|
c********t 发帖数: 5706 | 15 你和我的解法差不多,这个时间空间复杂度是多少?
【在 c*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢阿,过了 : public class Solution { : public boolean isInterleave(String s1, String s2, String s3) { : // Start typing your Java solution below : // DO NOT write main() function : int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); : if (l1+l2 != l3) return false; : if (s1.equals("")) return s2.equals(s3); : if (s2.equals("")) return s1.equals(s3); :
|
c********t 发帖数: 5706 | 16 这么简单怎么没想到呢。不过不是 if(s3 has it),而是s1,s3一起过,因为要考虑字母
顺序一致。
【在 a****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : s1 = "aabcc", : s2 = "dbbca", : When s3 = "aadbbcbcac". : for( each char in s1) { : if(s3 has it) { : remove it : } else { : return false : } : }
|
c**d 发帖数: 580 | 17 recursion就不是O(1)空间了。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用backtracking + recursion是O(n)时间,O(1)空间吗? : 我的48个case都过了,但是judge large超时了!
|
C***U 发帖数: 2406 | 18 肯定不是噢
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用backtracking + recursion是O(n)时间,O(1)空间吗? : 我的48个case都过了,但是judge large超时了!
|
C***U 发帖数: 2406 | 19 据说是google interview面试官要求。。。。
我肯定做不出来啊
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题为什么要找O(n)的解?
|
p*****2 发帖数: 21240 | 20
这题感觉O(n)不行呀。其实用DP做出来就挺好了。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 据说是google interview面试官要求。。。。 : 我肯定做不出来啊
|
|
|
C***U 发帖数: 2406 | 21 我的那个很奇怪
small用了12毫秒
large反而只要8毫秒
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用backtracking + recursion是O(n)时间,O(1)空间吗? : 我的48个case都过了,但是judge large超时了!
|
C***U 发帖数: 2406 | 22 我觉得不行 但是有人遇到这 还做出来了 我明天再去确认一下
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这题感觉O(n)不行呀。其实用DP做出来就挺好了。
|
a****a 发帖数: 15 | 23 yeah, I missed that
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这么简单怎么没想到呢。不过不是 if(s3 has it),而是s1,s3一起过,因为要考虑字母 : 顺序一致。
|
c********t 发帖数: 5706 | 24 啊,我的small要576 ms, 差距太大了。帮我看看我的时间空间复杂度是多少
public static boolean isInterleave(String s1, String s2, String s3) {
assert (s1 != null && s2 != null && s3 != null);
if (s3.length() != s1.length() + s2.length()) return false;
if (s1.isEmpty()) return s2.equals(s3);
if (s2.isEmpty()) return s1.equals(s3);
if (s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0))
return isInterleave(s1.substring(1), s2, s3.substring(1))
|| isInterleave(s1, s2.substring(1), s3.substring(1));
else if (s3.charAt(0) == s1.charAt(0))
return isInterleave(s1.substring(1), s2, s3.substring(1));
else if (s3.charAt(0) == s2.charAt(0))
return isInterleave(s1, s2.substring(1), s3.substring(1));
else
return false;
}
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的那个很奇怪 : small用了12毫秒 : large反而只要8毫秒
|
p*****2 发帖数: 21240 | 25
C++快吧
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啊,我的small要576 ms, 差距太大了。帮我看看我的时间空间复杂度是多少 : public static boolean isInterleave(String s1, String s2, String s3) { : assert (s1 != null && s2 != null && s3 != null); : if (s3.length() != s1.length() + s2.length()) return false; : if (s1.isEmpty()) return s2.equals(s3); : if (s2.isEmpty()) return s1.equals(s3); : : if (s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0)) : return isInterleave(s1.substring(1), s2, s3.substring(1)) : || isInterleave(s1, s2.substring(1), s3.substring(1));
|
C***U 发帖数: 2406 | 26 你可以去测试一下我的
也许我记错了
哈哈
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啊,我的small要576 ms, 差距太大了。帮我看看我的时间空间复杂度是多少 : public static boolean isInterleave(String s1, String s2, String s3) { : assert (s1 != null && s2 != null && s3 != null); : if (s3.length() != s1.length() + s2.length()) return false; : if (s1.isEmpty()) return s2.equals(s3); : if (s2.isEmpty()) return s1.equals(s3); : : if (s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0)) : return isInterleave(s1.substring(1), s2, s3.substring(1)) : || isInterleave(s1, s2.substring(1), s3.substring(1));
|
p*****2 发帖数: 21240 | 27
我测了一下
Run Status: Accepted!
Program Runtime: 0 milli secs
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你可以去测试一下我的 : 也许我记错了 : 哈哈
|
C***U 发帖数: 2406 | 28 主要是因为递归吧?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我测了一下 : Run Status: Accepted! : Program Runtime: 0 milli secs
|
C***U 发帖数: 2406 | 29 我的code?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我测了一下 : Run Status: Accepted! : Program Runtime: 0 milli secs
|
p*****2 发帖数: 21240 | 30
我用DP600多毫秒,Java。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要是因为递归吧?
|
|
|
p*****2 发帖数: 21240 | 31
你的。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的code?
|
C***U 发帖数: 2406 | 32 那就是java问题了。。。
不懂java....
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 你的。
|
p*****2 发帖数: 21240 | 33
java比C++要慢很多。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那就是java问题了。。。 : 不懂java....
|
C***U 发帖数: 2406 | 34 我的机器不如你的啊。。。
我这要10几。。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : java比C++要慢很多。
|
p*****2 发帖数: 21240 | 35
运行都是在leetcode的机器上运行的。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的机器不如你的啊。。。 : 我这要10几。。。。
|
C***U 发帖数: 2406 | 36 但是比如浏览器延误之类的 会算进去么?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 运行都是在leetcode的机器上运行的。
|
p*****2 发帖数: 21240 | 37
不会。你多试几次。平均值大数据应该还是慢。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 但是比如浏览器延误之类的 会算进去么?
|
C***U 发帖数: 2406 | 38 噢 好吧
应该是的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不会。你多试几次。平均值大数据应该还是慢。
|
c********t 发帖数: 5706 | 39 我晕,写完程序,发现你的想法是错的
aa
ab
abaa
s3-s1=ba != s2 return false
【在 a****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : yeah, I missed that
|
c********t 发帖数: 5706 | 40 你的速度和我的差不多,贴一个dp的codes看看,我的那个时间复杂度是 O(2^n)吗?
空间可不好算了,因为substring method本身就要开一个n空间给新的string吧?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不会。你多试几次。平均值大数据应该还是慢。
|
|
|
C***U 发帖数: 2406 | 41 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
请牛人指点1 2 |
c********t 发帖数: 5706 | 42 给个原题吧
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法 : 请牛人指点1 2
|
C***U 发帖数: 2406 | 43 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给个原题吧
|
c*****a 发帖数: 808 | 44 呃。。刚刚写的, 过不了 Progress: 47/48 test cases passed.
大牛看看有啥bug
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
if (l1+l2 != l3) return false;
if (s1.equals("")) return s2.equals(s3);
if (s2.equals("")) return s1.equals(s3);
while(l3 >0 && l2 >0 && l1>0){
if(s3.charAt(l3-1) != s2.charAt(l2-1) && s3.charAt(l3-1) != s1.
charAt(l1-1))
return false;
else
if(s3.charAt(l3-1) == s2.charAt(l2-1)){
l3--;
l2--;
}
else
if(s3.charAt(l3-1) == s1.charAt(l1-1)){
l3--;
l1--;
}
}
return true;
}
} |
e******o 发帖数: 757 | 45 what if s1[i]=s2[i]=s3[i]
【在 c*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃。。刚刚写的, 过不了 Progress: 47/48 test cases passed. : 大牛看看有啥bug : public class Solution { : public boolean isInterleave(String s1, String s2, String s3) { : // Start typing your Java solution below : // DO NOT write main() function : int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); : if (l1+l2 != l3) return false; : if (s1.equals("")) return s2.equals(s3); : if (s2.equals("")) return s1.equals(s3);
|
C***U 发帖数: 2406 | 46 跑一下这个例子
s3: abaa
s1: aa
s2: ba
【在 c*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 呃。。刚刚写的, 过不了 Progress: 47/48 test cases passed. : 大牛看看有啥bug : public class Solution { : public boolean isInterleave(String s1, String s2, String s3) { : // Start typing your Java solution below : // DO NOT write main() function : int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); : if (l1+l2 != l3) return false; : if (s1.equals("")) return s2.equals(s3); : if (s2.equals("")) return s1.equals(s3);
|
l***i 发帖数: 1309 | 47 Mine is O(n^2) and passed, how do you do O(n) time? |
e******o 发帖数: 757 | 48 same here
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Mine is O(n^2) and passed, how do you do O(n) time?
|
c*****a 发帖数: 808 | 49 感谢阿,过了
public class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
// Start typing your Java solution below
// DO NOT write main() function
int l1 = s1.length(), l2 = s2.length(), l3 = s3.length();
if (l1+l2 != l3) return false;
if (s1.equals("")) return s2.equals(s3);
if (s2.equals("")) return s1.equals(s3);
if(s3.charAt(l3-1) != s2.charAt(l2-1) && s3.charAt(l3-1) != s1.
charAt(l1-1))
return false;
if(s3.charAt(l3-1) == s2.charAt(l2-1) && s3.charAt(l3-1) == s1.
charAt(l1-1)){
return isInterleave(s1, s2.substring(0, l2 - 1), s3.substring(0,
l3 - 1)) ||
isInterleave(s1.substring(0, l1-1), s2, s3.substring(0,
l3-1)) ;
}
if(s3.charAt(l3-1) == s2.charAt(l2-1))
return isInterleave(s1, s2.substring(0, l2 - 1), s3.substring(0,
l3 - 1));
if(s3.charAt(l3-1) == s1.charAt(l1-1))
return isInterleave(s1.substring(0, l1-1), s2, s3.substring(0,
l3-1)) ;
return true;
}
} |
C***U 发帖数: 2406 | 50 我这不是来询问的么。。。。呵呵
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Mine is O(n^2) and passed, how do you do O(n) time?
|
|
|
C***U 发帖数: 2406 | 51 我能想到的就是O(n^2)时间 O(n)空间的
bool isInterleaveNew(string s1, string s2, string s3) {
vector possibleIndex;
vector tempIndex;
if(s1.empty()) {
return s2 == s3;
}
if(s2.empty()) {
return s1 == s3;
}
if(s1.size() + s2.size() != s3.size()) {
return false;
}
if(s1[0] != s3[0] && s2[0] != s3[0]) {
return false;
}
else {
if(s2[0] == s3[0]) {
possibleIndex.push_back(-1);
}
if(s1[0] == s3[0]) {
possibleIndex.push_back(0);
}
}
for(int i = 1; i < s3.size(); i++) {
for(int j = 0; j < possibleIndex.size(); j++) {
int k = possibleIndex[j];
if(i - k - 1 < s2.size() && s2[i - k - 1] == s3[i] && (tempIndex
.empty() || (!tempIndex.empty() && tempIndex[tempIndex.size() - 1] != k))) {
tempIndex.push_back(k);
}
if(k + 1 < s1.size() && s1[k + 1] == s3[i]) {
tempIndex.push_back(k + 1);
}
}
possibleIndex = tempIndex;
tempIndex.clear();
if(possibleIndex.empty()) {
return false;
}
}
return true;
}
【在 l***i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Mine is O(n^2) and passed, how do you do O(n) time?
|
p*****2 发帖数: 21240 | |
a****a 发帖数: 15 | 53 s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac".
for( each char in s1) {
if(s3 has it) {
remove it
} else {
return false
}
}
return (s3==s2) |
c********t 发帖数: 5706 | 54 用backtracking + recursion是O(n)时间,O(1)空间吗?
我的48个case都过了,但是judge large超时了!
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法 : 请牛人指点1 2
|
c********t 发帖数: 5706 | 55 你和我的解法差不多,这个时间空间复杂度是多少?
【在 c*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感谢阿,过了 : public class Solution { : public boolean isInterleave(String s1, String s2, String s3) { : // Start typing your Java solution below : // DO NOT write main() function : int l1 = s1.length(), l2 = s2.length(), l3 = s3.length(); : if (l1+l2 != l3) return false; : if (s1.equals("")) return s2.equals(s3); : if (s2.equals("")) return s1.equals(s3); :
|
c********t 发帖数: 5706 | 56 这么简单怎么没想到呢。不过不是 if(s3 has it),而是s1,s3一起过,因为要考虑字母
顺序一致。
【在 a****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : s1 = "aabcc", : s2 = "dbbca", : When s3 = "aadbbcbcac". : for( each char in s1) { : if(s3 has it) { : remove it : } else { : return false : } : }
|
c**d 发帖数: 580 | 57 recursion就不是O(1)空间了。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用backtracking + recursion是O(n)时间,O(1)空间吗? : 我的48个case都过了,但是judge large超时了!
|
C***U 发帖数: 2406 | 58 肯定不是噢
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用backtracking + recursion是O(n)时间,O(1)空间吗? : 我的48个case都过了,但是judge large超时了!
|
C***U 发帖数: 2406 | 59 据说是google interview面试官要求。。。。
我肯定做不出来啊
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这题为什么要找O(n)的解?
|
p*****2 发帖数: 21240 | 60
这题感觉O(n)不行呀。其实用DP做出来就挺好了。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 据说是google interview面试官要求。。。。 : 我肯定做不出来啊
|
|
|
C***U 发帖数: 2406 | 61 我的那个很奇怪
small用了12毫秒
large反而只要8毫秒
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用backtracking + recursion是O(n)时间,O(1)空间吗? : 我的48个case都过了,但是judge large超时了!
|
C***U 发帖数: 2406 | 62 我觉得不行 但是有人遇到这 还做出来了 我明天再去确认一下
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 这题感觉O(n)不行呀。其实用DP做出来就挺好了。
|
a****a 发帖数: 15 | 63 yeah, I missed that
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这么简单怎么没想到呢。不过不是 if(s3 has it),而是s1,s3一起过,因为要考虑字母 : 顺序一致。
|
c********t 发帖数: 5706 | 64 啊,我的small要576 ms, 差距太大了。帮我看看我的时间空间复杂度是多少
public static boolean isInterleave(String s1, String s2, String s3) {
assert (s1 != null && s2 != null && s3 != null);
if (s3.length() != s1.length() + s2.length()) return false;
if (s1.isEmpty()) return s2.equals(s3);
if (s2.isEmpty()) return s1.equals(s3);
if (s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0))
return isInterleave(s1.substring(1), s2, s3.substring(1))
|| isInterleave(s1, s2.substring(1), s3.substring(1));
else if (s3.charAt(0) == s1.charAt(0))
return isInterleave(s1.substring(1), s2, s3.substring(1));
else if (s3.charAt(0) == s2.charAt(0))
return isInterleave(s1, s2.substring(1), s3.substring(1));
else
return false;
}
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的那个很奇怪 : small用了12毫秒 : large反而只要8毫秒
|
p*****2 发帖数: 21240 | 65
C++快吧
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啊,我的small要576 ms, 差距太大了。帮我看看我的时间空间复杂度是多少 : public static boolean isInterleave(String s1, String s2, String s3) { : assert (s1 != null && s2 != null && s3 != null); : if (s3.length() != s1.length() + s2.length()) return false; : if (s1.isEmpty()) return s2.equals(s3); : if (s2.isEmpty()) return s1.equals(s3); : : if (s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0)) : return isInterleave(s1.substring(1), s2, s3.substring(1)) : || isInterleave(s1, s2.substring(1), s3.substring(1));
|
C***U 发帖数: 2406 | 66 你可以去测试一下我的
也许我记错了
哈哈
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 啊,我的small要576 ms, 差距太大了。帮我看看我的时间空间复杂度是多少 : public static boolean isInterleave(String s1, String s2, String s3) { : assert (s1 != null && s2 != null && s3 != null); : if (s3.length() != s1.length() + s2.length()) return false; : if (s1.isEmpty()) return s2.equals(s3); : if (s2.isEmpty()) return s1.equals(s3); : : if (s3.charAt(0) == s1.charAt(0) && s3.charAt(0) == s2.charAt(0)) : return isInterleave(s1.substring(1), s2, s3.substring(1)) : || isInterleave(s1, s2.substring(1), s3.substring(1));
|
p*****2 发帖数: 21240 | 67
我测了一下
Run Status: Accepted!
Program Runtime: 0 milli secs
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你可以去测试一下我的 : 也许我记错了 : 哈哈
|
C***U 发帖数: 2406 | 68 主要是因为递归吧?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我测了一下 : Run Status: Accepted! : Program Runtime: 0 milli secs
|
C***U 发帖数: 2406 | 69 我的code?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 我测了一下 : Run Status: Accepted! : Program Runtime: 0 milli secs
|
p*****2 发帖数: 21240 | 70
我用DP600多毫秒,Java。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 主要是因为递归吧?
|
|
|
p*****2 发帖数: 21240 | 71
你的。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的code?
|
C***U 发帖数: 2406 | 72 那就是java问题了。。。
不懂java....
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 你的。
|
p*****2 发帖数: 21240 | 73
java比C++要慢很多。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 那就是java问题了。。。 : 不懂java....
|
C***U 发帖数: 2406 | 74 我的机器不如你的啊。。。
我这要10几。。。。
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : java比C++要慢很多。
|
p*****2 发帖数: 21240 | 75
运行都是在leetcode的机器上运行的。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的机器不如你的啊。。。 : 我这要10几。。。。
|
C***U 发帖数: 2406 | 76 但是比如浏览器延误之类的 会算进去么?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 运行都是在leetcode的机器上运行的。
|
p*****2 发帖数: 21240 | 77
不会。你多试几次。平均值大数据应该还是慢。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 但是比如浏览器延误之类的 会算进去么?
|
C***U 发帖数: 2406 | 78 噢 好吧
应该是的
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不会。你多试几次。平均值大数据应该还是慢。
|
c********t 发帖数: 5706 | 79 我晕,写完程序,发现你的想法是错的
aa
ab
abaa
s3-s1=ba != s2 return false
【在 a****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : yeah, I missed that
|
c********t 发帖数: 5706 | 80 你的速度和我的差不多,贴一个dp的codes看看,我的那个时间复杂度是 O(2^n)吗?
空间可不好算了,因为substring method本身就要开一个n空间给新的string吧?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 不会。你多试几次。平均值大数据应该还是慢。
|
|
|
c********t 发帖数: 5706 | 81 大侠,拿到g offer了吗?
我重新研究这题,不可能有O(n)时间解法。DP解法是O(m*n)时间,O(m*n)空间 m is s1
length, n is s2 length。
还是没懂你的codes,如何做到O(n)空间,能解释一下吗?
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我能想到的就是O(n^2)时间 O(n)空间的 : bool isInterleaveNew(string s1, string s2, string s3) { : vector possibleIndex; : vector tempIndex; : if(s1.empty()) { : return s2 == s3; : } : if(s2.empty()) { : return s1 == s3; : }
|
C***U 发帖数: 2406 | 82 就是一个数组记录当前的可能情况
然后记录下一个数组
把前一个数组扔掉
周五给正式结果
各种紧张中!!!!
s1
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大侠,拿到g offer了吗? : 我重新研究这题,不可能有O(n)时间解法。DP解法是O(m*n)时间,O(m*n)空间 m is s1 : length, n is s2 length。 : 还是没懂你的codes,如何做到O(n)空间,能解释一下吗?
|
c**s 发帖数: 23 | 83 public boolean isInterleave(char[] s1, int i1, char[] s2, int i2, char[] s3,
int i3) {
if (i3 == s3.length) {
if (i1 == s1.length && i2 == s2.length) return true;
return false;
}
if (i1 < s1.length && s1[i1] == s3[i3] && this.isInterleave(s1, i1 + 1, s2
, i2, s3, i3 + 1))
return true;
if (i2 < s2.length && s2[i2] == s3[i3] && this.isInterleave(s2, i2 + 1, s1
, i1, s3, i3 + 1))
return true;
return false;
}
public boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null)
return false;
return this.isInterleave(s1.toCharArray(), 0, s2.toCharArray(), 0,
s3.toCharArray(), 0) ||
this.isInterleave(s2.toCharArray(), 0, s1.toCharArray(), 0,
s3.toCharArray(), 0);
} |
c**s 发帖数: 23 | 84 Passed all short cases, long case took 2-3 seconds.
s3,
s2
s1
【在 c**s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : public boolean isInterleave(char[] s1, int i1, char[] s2, int i2, char[] s3, : int i3) { : if (i3 == s3.length) { : if (i1 == s1.length && i2 == s2.length) return true; : return false; : } : if (i1 < s1.length && s1[i1] == s3[i3] && this.isInterleave(s1, i1 + 1, s2 : , i2, s3, i3 + 1)) : return true; : if (i2 < s2.length && s2[i2] == s3[i3] && this.isInterleave(s2, i2 + 1, s1
|
c**s 发帖数: 23 | 85 Bummer,
"Run Status: Time Limit Exceeded"
It took 3 seconds on my PC tough
【在 c**s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Passed all short cases, long case took 2-3 seconds. : : s3, : s2 : s1
|
c**s 发帖数: 23 | 86 // DP version
public boolean isInterleave(String s1, String s2, String s3) {
if (s3.length() != s1.length() + s2.length())
return false;
char[] s1c = s1.toCharArray();
char[] s2c = s2.toCharArray();
char[] s3c = s3.toCharArray();
boolean board[][] = new boolean[s1.length() + 1][s2.length() + 1];
board[0][0] = true;
for (int i = 1; i <= s1.length(); i++)
board[i][0] = board[i - 1][0] && s1c[i - 1] == s3c[i - 1];
for (int j = 1; j <= s2.length(); j++)
board[0][j] = board[0][j - 1] && s2c[j - 1] == s3c[j - 1];
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
board[i][j] = (board[i - 1][j] && (s1c[i - 1] == s3c[i + j - 1])) || (
board[i][j - 1] && s2c[j - 1] == s3c[i + j - 1]);
}
}
return board[s1.length()][s2.length()];
} |
c********t 发帖数: 5706 | 87 bless.
可惜我已收到电锯。
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是一个数组记录当前的可能情况 : 然后记录下一个数组 : 把前一个数组扔掉 : 周五给正式结果 : 各种紧张中!!!! : : s1
|
e***s 发帖数: 799 | 88 Bless~
【在 C***U 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 就是一个数组记录当前的可能情况 : 然后记录下一个数组 : 把前一个数组扔掉 : 周五给正式结果 : 各种紧张中!!!! : : s1
|