C***U
发帖数: 2406 | 1 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
请牛人指点1 2 |
c********t
发帖数: 5706 | 2 给个原题吧
【在 C***U 的大作中提到】
: 听别人说有 没想出来 只能想到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 的大作中提到】
: 给个原题吧
|
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 的大作中提到】
: 呃。。刚刚写的， 过不了 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 的大作中提到】
: 呃。。刚刚写的， 过不了 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
: 请牛人指点1 2
|
c********t
发帖数: 5706 | 15 你和我的解法差不多，这个时间空间复杂度是多少？
【在 c*****a 的大作中提到】
: 感谢阿，过了
: 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 的大作中提到】
: 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 的大作中提到】
: 用backtracking + recursion是O(n)时间，O(1)空间吗？
: 我的48个case都过了，但是judge large超时了！
|
C***U
发帖数: 2406 | 18 肯定不是噢
【在 c********t 的大作中提到】
: 用backtracking + recursion是O(n)时间，O(1)空间吗？
: 我的48个case都过了，但是judge large超时了！
|
C***U
发帖数: 2406 | 19 据说是google interview面试官要求。。。。
我肯定做不出来啊
【在 p*****2 的大作中提到】
: 这题为什么要找O(n)的解？
|
p*****2
发帖数: 21240 | 20
这题感觉O(n)不行呀。其实用DP做出来就挺好了。
【在 C***U 的大作中提到】
: 据说是google interview面试官要求。。。。
: 我肯定做不出来啊
|
|
|
C***U
发帖数: 2406 | 21 我的那个很奇怪
small用了12毫秒
large反而只要8毫秒
【在 c********t 的大作中提到】
: 用backtracking + recursion是O(n)时间，O(1)空间吗？
: 我的48个case都过了，但是judge large超时了！
|
C***U
发帖数: 2406 | 22 我觉得不行 但是有人遇到这 还做出来了 我明天再去确认一下
【在 p*****2 的大作中提到】
:
: 这题感觉O(n)不行呀。其实用DP做出来就挺好了。
|
a****a
发帖数: 15 | 23 yeah, I missed that
【在 c********t 的大作中提到】
: 这么简单怎么没想到呢。不过不是 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 的大作中提到】
: 我的那个很奇怪
: small用了12毫秒
: large反而只要8毫秒
|
p*****2
发帖数: 21240 | 25
C++快吧
【在 c********t 的大作中提到】
: 啊，我的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 的大作中提到】
: 啊，我的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 的大作中提到】
: 你可以去测试一下我的
: 也许我记错了
: 哈哈
|
C***U
发帖数: 2406 | 28 主要是因为递归吧?
【在 p*****2 的大作中提到】
:
: 我测了一下
: Run Status: Accepted!
: Program Runtime: 0 milli secs
|
C***U
发帖数: 2406 | 29 我的code?
【在 p*****2 的大作中提到】
:
: 我测了一下
: Run Status: Accepted!
: Program Runtime: 0 milli secs
|
p*****2
发帖数: 21240 | 30
我用DP600多毫秒，Java。
【在 C***U 的大作中提到】
: 主要是因为递归吧?
|
|
|
p*****2
发帖数: 21240 | 31
你的。
【在 C***U 的大作中提到】
: 我的code?
|
C***U
发帖数: 2406 | 32 那就是java问题了。。。
不懂java....
【在 p*****2 的大作中提到】
:
: 你的。
|
p*****2
发帖数: 21240 | 33
java比C＋＋要慢很多。
【在 C***U 的大作中提到】
: 那就是java问题了。。。
: 不懂java....
|
C***U
发帖数: 2406 | 34 我的机器不如你的啊。。。
我这要10几。。。。
【在 p*****2 的大作中提到】
:
: java比C＋＋要慢很多。
|
p*****2
发帖数: 21240 | 35
运行都是在leetcode的机器上运行的。
【在 C***U 的大作中提到】
: 我的机器不如你的啊。。。
: 我这要10几。。。。
|
C***U
发帖数: 2406 | 36 但是比如浏览器延误之类的 会算进去么?
【在 p*****2 的大作中提到】
:
: 运行都是在leetcode的机器上运行的。
|
p*****2
发帖数: 21240 | 37
不会。你多试几次。平均值大数据应该还是慢。
【在 C***U 的大作中提到】
: 但是比如浏览器延误之类的 会算进去么?
|
C***U
发帖数: 2406 | 38 噢 好吧
应该是的
【在 p*****2 的大作中提到】
:
: 不会。你多试几次。平均值大数据应该还是慢。
|
c********t
发帖数: 5706 | 39 我晕，写完程序，发现你的想法是错的
aa
ab
abaa
s3-s1=ba != s2 return false
【在 a****a 的大作中提到】
: yeah, I missed that
|
c********t
发帖数: 5706 | 40 你的速度和我的差不多，贴一个dp的codes看看，我的那个时间复杂度是 O(2^n）吗？
空间可不好算了，因为substring method本身就要开一个n空间给新的string吧？
【在 p*****2 的大作中提到】
:
: 不会。你多试几次。平均值大数据应该还是慢。
|
|
|
C***U
发帖数: 2406 | 41 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
请牛人指点1 2 |
c********t
发帖数: 5706 | 42 给个原题吧
【在 C***U 的大作中提到】
: 听别人说有 没想出来 只能想到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 的大作中提到】
: 给个原题吧
|
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 的大作中提到】
: 呃。。刚刚写的， 过不了 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 的大作中提到】
: 呃。。刚刚写的， 过不了 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 听别人说有 没想出来 只能想到O(n^2)时间O(n)空间的算法
: 请牛人指点1 2
|
c********t
发帖数: 5706 | 55 你和我的解法差不多，这个时间空间复杂度是多少？
【在 c*****a 的大作中提到】
: 感谢阿，过了
: 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 的大作中提到】
: 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 的大作中提到】
: 用backtracking + recursion是O(n)时间，O(1)空间吗？
: 我的48个case都过了，但是judge large超时了！
|
C***U
发帖数: 2406 | 58 肯定不是噢
【在 c********t 的大作中提到】
: 用backtracking + recursion是O(n)时间，O(1)空间吗？
: 我的48个case都过了，但是judge large超时了！
|
C***U
发帖数: 2406 | 59 据说是google interview面试官要求。。。。
我肯定做不出来啊
【在 p*****2 的大作中提到】
: 这题为什么要找O(n)的解？
|
p*****2
发帖数: 21240 | 60
这题感觉O(n)不行呀。其实用DP做出来就挺好了。
【在 C***U 的大作中提到】
: 据说是google interview面试官要求。。。。
: 我肯定做不出来啊
|
|
|
C***U
发帖数: 2406 | 61 我的那个很奇怪
small用了12毫秒
large反而只要8毫秒
【在 c********t 的大作中提到】
: 用backtracking + recursion是O(n)时间，O(1)空间吗？
: 我的48个case都过了，但是judge large超时了！
|
C***U
发帖数: 2406 | 62 我觉得不行 但是有人遇到这 还做出来了 我明天再去确认一下
【在 p*****2 的大作中提到】
:
: 这题感觉O(n)不行呀。其实用DP做出来就挺好了。
|
a****a
发帖数: 15 | 63 yeah, I missed that
【在 c********t 的大作中提到】
: 这么简单怎么没想到呢。不过不是 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 的大作中提到】
: 我的那个很奇怪
: small用了12毫秒
: large反而只要8毫秒
|
p*****2
发帖数: 21240 | 65
C++快吧
【在 c********t 的大作中提到】
: 啊，我的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 的大作中提到】
: 啊，我的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 的大作中提到】
: 你可以去测试一下我的
: 也许我记错了
: 哈哈
|
C***U
发帖数: 2406 | 68 主要是因为递归吧?
【在 p*****2 的大作中提到】
:
: 我测了一下
: Run Status: Accepted!
: Program Runtime: 0 milli secs
|
C***U
发帖数: 2406 | 69 我的code?
【在 p*****2 的大作中提到】
:
: 我测了一下
: Run Status: Accepted!
: Program Runtime: 0 milli secs
|
p*****2
发帖数: 21240 | 70
我用DP600多毫秒，Java。
【在 C***U 的大作中提到】
: 主要是因为递归吧?
|
|
|
p*****2
发帖数: 21240 | 71
你的。
【在 C***U 的大作中提到】
: 我的code?
|
C***U
发帖数: 2406 | 72 那就是java问题了。。。
不懂java....
【在 p*****2 的大作中提到】
:
: 你的。
|
p*****2
发帖数: 21240 | 73
java比C＋＋要慢很多。
【在 C***U 的大作中提到】
: 那就是java问题了。。。
: 不懂java....
|
C***U
发帖数: 2406 | 74 我的机器不如你的啊。。。
我这要10几。。。。
【在 p*****2 的大作中提到】
:
: java比C＋＋要慢很多。
|
p*****2
发帖数: 21240 | 75
运行都是在leetcode的机器上运行的。
【在 C***U 的大作中提到】
: 我的机器不如你的啊。。。
: 我这要10几。。。。
|
C***U
发帖数: 2406 | 76 但是比如浏览器延误之类的 会算进去么?
【在 p*****2 的大作中提到】
:
: 运行都是在leetcode的机器上运行的。
|
p*****2
发帖数: 21240 | 77
不会。你多试几次。平均值大数据应该还是慢。
【在 C***U 的大作中提到】
: 但是比如浏览器延误之类的 会算进去么?
|
C***U
发帖数: 2406 | 78 噢 好吧
应该是的
【在 p*****2 的大作中提到】
:
: 不会。你多试几次。平均值大数据应该还是慢。
|
c********t
发帖数: 5706 | 79 我晕，写完程序，发现你的想法是错的
aa
ab
abaa
s3-s1=ba != s2 return false
【在 a****a 的大作中提到】
: yeah, I missed that
|
c********t
发帖数: 5706 | 80 你的速度和我的差不多，贴一个dp的codes看看，我的那个时间复杂度是 O(2^n）吗？
空间可不好算了，因为substring method本身就要开一个n空间给新的string吧？
【在 p*****2 的大作中提到】
:
: 不会。你多试几次。平均值大数据应该还是慢。
|
|
|
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 的大作中提到】
: 我能想到的就是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 的大作中提到】
: 大侠，拿到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 的大作中提到】
: 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 的大作中提到】
: 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 的大作中提到】
: 就是一个数组记录当前的可能情况
: 然后记录下一个数组
: 把前一个数组扔掉
: 周五给正式结果
: 各种紧张中！！！！
:
: s1
|
e***s
发帖数: 799 | 88 Bless～
【在 C***U 的大作中提到】
: 就是一个数组记录当前的可能情况
: 然后记录下一个数组
: 把前一个数组扔掉
: 周五给正式结果
: 各种紧张中！！！！
:
: s1
|
