|
p*****2
发帖数: 21240 | 2
其实就是个低级错误
for (int i = 0; i < 1; i++) |
|
|
p*****2
发帖数: 21240 | 4 不过感觉C＋＋写起来还是比Java罗嗦一些。不过C＋＋有指针，有些题就做的很灵活，
简洁。 |
|
|
|
b***m
发帖数: 5987 | 7
吃饭归吃饭，吃饭讲不清楚，吃完饭继续讲呀。我住Kirkland，平常就在Main Campus
周边转悠。 |
|
p*****2
发帖数: 21240 | 8
貌似以前面过我。我没做出来，不过最后还是给了我onsite了。 |
|
|
|
|
|
b***m
发帖数: 5987 | 13 这个想写好还真不容易，看来我今天做题也不算太差。 |
|
l*********8
发帖数: 4642 | 14 刚才写了这个，通过了leetcode大数据量测试
bool isMatch(const char *s, const char *p) {
if (!p) return !s;
if (!s) return !p;
for (const char *star=NULL, *s_save=s; *s; ) {
if (*p == '*') {
star = p++;
s_save = s;
} else if ( *p != '?' && *s != *p) {
if (!star) {
return false;
} else {
p = star+1;
s = ++s_save;
}
} else {
s++;
p++;
}
}
while (*p == '*') p++;
return !*p;
} |
|
|
p*****2
发帖数: 21240 | 16
longway，你写这个大概花了多少时间呀？ |
|
l*********8
发帖数: 4642 | 17 不敢当，我刚才写的时候，开始也挺晕的，要是刚才是面试就挂在白板上了。 |
|
|
l*********8
发帖数: 4642 | 19 哎，刚才花了45分钟才写对吧。。。面试就挂了。 |
|
|
l*********8
发帖数: 4642 | 21 我加了注释
bool isMatch(const char *s, const char *p) {
if (!p) return !s;
if (!s) return !p;
for (const char *star=NULL, *s_save=s; *s; ) {
// star是上一个*出现的位置；s_save+1是出现不匹配时，s应该回到的位置。
if (*p == '*') {
star = p++;
s_save = s;
} else if ( *p != '?' && *s != *p) { // 不匹配
if (!star) { // 没有*来做灵活匹配
return false;
} else { // 有*， 回到star+1 和 s_save+1匹配
p = star+1;
s = ++s_save;
}
} else { // 匹配时，p和s都前进... 阅读全帖 |
|
p*****2
发帖数: 21240 | 22
很牛了。我刚才试着写了一下，最好的是过了80多个test case，调不通，感觉水很深
，就改DP了。不过这东西我感觉面试真不容易写的bug free。 |
|
b***m
发帖数: 5987 | 23
多谢！核心语句其实就是这句：
if (!star) { // 没有*来做灵活匹配
return false;
} else { // 有*， 回到star+1 和 s_save+1匹配
p = star+1;
s = ++s_save;
}
一旦不匹配又有过往的*，那么就把p回溯到上个*的下一个字符，把s回溯到p出现*时s
对应的下一个字符，对吗？ |
|
l*********8
发帖数: 4642 | 24 差不多，不过不仅仅是“把s回溯到p出现*时s对应的下一个字符”。 一直不能匹配的
时候，s_save也一直增加，就跟简单字符串匹配差不多。
s |
|
l*********8
发帖数: 4642 | 25 恩，这个题没好好写过的话，面试真不容易写。 我第一次写了通过OJ的时候，好像写
了六七十行。。。。。 |
|
b***m
发帖数: 5987 | 26 就是说一旦开始不匹配，就用那个*一点点地往后吃不匹配字符，直到又出现匹配？ |
|
p*****2
发帖数: 21240 | 27 我用Java写了一个，真是没有C＋＋简洁呀。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
int i=0;
int j=0;
int star=-1;
int sp=0;
while(i
{
//one * and multiple *, same effect
while(j
{
star=j++; //* match 0 character
sp=i;
}
if(j==m || (p.charAt(j)!=s.charAt(i) && p.ch... 阅读全帖 |
|
|
b***m
发帖数: 5987 | 29
想法不错，代码也很整洁易懂，是O(n)时间复杂度吗？ |
|
h****n
发帖数: 1093 | 30 应该不是O（n）有回溯了 最坏情况下应该也有n^2了貌似？ |
|
|
l*******b
发帖数: 2586 | 32 另外各种限制条件很难写的题目感觉不会写
Restore IP Addresses
Wildcard Matching
Word Search
Sudoku两个题费了老大劲写完了，有140多行，汗
Scramble String
Distinct Subsequences
这两个DP的也没治，感觉比longest common subsequence, edit distance这类难多了 |
|
f*******t
发帖数: 7549 | 33 java有些题怎么都ac不了，比如wildcard matching和common prefix。谁有能ac的代码
希望贡献出来膜拜一下 |
|
c********t
发帖数: 5706 | 34 写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
isMatch("aab", "c*a*b") → false
isMatch（"mississippi", "m*si*"）竟然是true? |
|
a****x
发帖数: 89 | 35 因为* match any length of string.
isMatch("aab", "c*a*b") → false: "aab" 里没有'c',所以不可能match;
isMatch（"mississippi", "m*si*"）: 第一个* match "issis", 第二个* match "ppi
".
谁有greedy的solution可以参考下吗？ |
|
t****a
发帖数: 1212 | 36 这题怎么用greedy来做呢？DP的话是n*m计算量
memoize dp的解
(defn is-match [str1 str2]
(let [str1a (str str1 \a)
str2a (str str2 \a)
n1 (count str1a)
n2 (count str2a)
seq2 (apply concat (repeat n1 (range n2 -1 -1)))
seq1 (mapcat #(repeat n2 %) (range n1 -1 -1))
]
(do
(def is-match-rec
(memoize
(fn [i1 i2]
(let [l1 (- n1 i1)
l2 (- n2 i2)]
(cond (and (== 0 l1) (== 0 l2)) true
(or (=... 阅读全帖 |
|
l**b
发帖数: 457 | 37 楼主把这道题目和regular expression matching那题的意思混淆了吧。这个里面的“*
”和preceding character没有任何关系的。和regular expression matching不同的。 |
|
c********t
发帖数: 5706 | 38 哦，是的。又土了。
“*
★ 发自iPhone App: ChineseWeb 7.7 |
|
c********t
发帖数: 5706 | 39 用java写了一个DP, 竟然judge large的时候，Memory Limit Exceeded。 |
|
f*******t
发帖数: 7549 | 40 问过1337哥，他说最大数据是32768*32768，肯定会MLE。
我有个优化的版本，但最后一个test case还是TLE。十分想看谁有能AC的代码！
public boolean isMatch(String s, String p) {
if (s == null || p == null)
return false;
if (s.isEmpty() && p.isEmpty()) { //Both are empty string -> true
return true;
} else if (s.isEmpty()) { // If s is empty, p must not contain
any character other than '*'
for (int i = 0; i < p.length(); i++) {
if (p.charAt(i) != '*')
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 41 这题greedy的很难写。等我总结到的时候再写吧。感觉面试DP就可以了。 |
|
c********t
发帖数: 5706 | 42 恩，滚动二维数组用得好。考古发现dp解法没有accepted的。 greedy才行。 longway
和peking2都给了代码。
true
★ 发自iPhone App: ChineseWeb 7.7 |
|
|
|
f*******t
发帖数: 7549 | 45 改版那天我看到这个c++解法了，跟我的差不多。 |
|
|
c********t
发帖数: 5706 | 47 二爷，新浪leetcode微博，是你的还是ihasleetcode的？ |
|
p*****2
发帖数: 21240 | 48
是我的。抢了leetcode的ID了。哈哈。 |
|
t**********h
发帖数: 2273 | 49 那上面的peking2的微博是leetcode抢了？ |
|
c********t
发帖数: 5706 | 50 二爷，greedy的解法时间复杂度是多少？我看好像worst case也是O(m*n)啊,为什么就
能过最大那个test case呢？ |
|
