c********t
发帖数: 5706 | 1 写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
isMatch("aab", "c*a*b") → false
isMatch（"mississippi", "m*si*"）竟然是true? |
a****x
发帖数: 89 | 2 因为* match any length of string.
isMatch("aab", "c*a*b") → false: "aab" 里没有'c',所以不可能match;
isMatch（"mississippi", "m*si*"）: 第一个* match "issis", 第二个* match "ppi
".
谁有greedy的solution可以参考下吗？
【在 c********t 的大作中提到】
: 写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
: isMatch("aab", "c*a*b") → false
: isMatch（"mississippi", "m*si*"）竟然是true?
|
t****a
发帖数: 1212 | 3 这题怎么用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 (== 0 l1) (== 0 l2)) false
:else (let [c1 (get str1a i1)
c2 (get str2a i2)
j1 (inc i1)
j2 (inc i2)]
(cond (= c2 \?) (is-match-rec j1 j2)
(= c2 \*) (or (is-match-rec i1 j2)
(is-match-rec j1 i2))
:else (if (= c1 c2)
(is-match-rec j1 j2)
false))))))))
(let [r (map is-match-rec seq1 seq2)]
(last r)))))
;; small data
(is-match "abcde" "abc*?") ; true
(is-match "abcd" "*?*?*?*?") ; true
(is-match "abc" "*?*?*?*?") ; false
(is-match "mississippi" "m*issip*") ; true
(is-match "mississippi" "m*i*si*si*pis") ; false
;; large data
(is-match "aaaaaaaaaaaaaaac" "*aaaaaaaaaaaaaaa*b") ; false
(is-match "bbaaababbaaababababbb" "*a*****bb") ; true
(is-match "baabaaabbaaaaabababbbbaabbaaabaababbababbaababbaabbb" "*bbb***a*
baa*bab**bb") ; true
ppi
【在 a****x 的大作中提到】
: 因为* match any length of string.
: isMatch("aab", "c*a*b") → false: "aab" 里没有'c',所以不可能match;
: isMatch（"mississippi", "m*si*"）: 第一个* match "issis", 第二个* match "ppi
: ".
: 谁有greedy的solution可以参考下吗？
|
l**b
发帖数: 457 | 4 楼主把这道题目和regular expression matching那题的意思混淆了吧。这个里面的“*
”和preceding character没有任何关系的。和regular expression matching不同的。
【在 c********t 的大作中提到】
: 写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
: isMatch("aab", "c*a*b") → false
: isMatch（"mississippi", "m*si*"）竟然是true?
|
c********t
发帖数: 5706 | 5 哦，是的。又土了。
“*
★ 发自iPhone App: ChineseWeb 7.7
【在 l**b 的大作中提到】
: 楼主把这道题目和regular expression matching那题的意思混淆了吧。这个里面的“*
: ”和preceding character没有任何关系的。和regular expression matching不同的。
|
c********t
发帖数: 5706 | 6 用java写了一个DP, 竟然judge large的时候，Memory Limit Exceeded。
【在 t****a 的大作中提到】
: 这题怎么用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))
: ]
|
f*******t
发帖数: 7549 | 7 问过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) != '*')
return false;
}
return true;
} else if (p.isEmpty()) { // If p is empty, return false
return false;
}
char[] pArr = p.toCharArray();
char[] sArr = s.toCharArray();
// handles test cases like s = "c", p = "*?*?"
int leadingStars = -1;
while (++leadingStars < pArr.length && pArr[leadingStars] == '*') {}
leadingStars--;
boolean[][] T = new boolean[2][pArr.length];
for (int i = 0; i < sArr.length; i++) {
for (int j = 0; j < pArr.length; j++) {
char c = pArr[j];
if (c == '*') {
T[1][j] = (i > 0 ? T[0][j] : false)
|| ((i > 0 && j > 0) ? T[0][j-1] : false)
|| (j > 0 ? T[1][j-1] : true)
|| ((i == 0 && j == 0) ? true : false);
} else if (c == '?' || c == sArr[i]) {
T[1][j] = ((i > 0 && j > 0) ? T[0][j-1] : false)
|| ((i == 0 && j == 0) ? true : false)
|| ((leadingStars >= 0 && leadingStars == j - 1)
? true : false);
} else {
T[1][j] = false;
}
}
boolean[] temp = T[0];
T[0] = T[1];
T[1] = temp;
}
return T[0][pArr.length-1];
}
【在 c********t 的大作中提到】
: 用java写了一个DP, 竟然judge large的时候，Memory Limit Exceeded。
|
p*****2
发帖数: 21240 | 8 这题greedy的很难写。等我总结到的时候再写吧。感觉面试DP就可以了。 |
c********t
发帖数: 5706 | 9 恩，滚动二维数组用得好。考古发现dp解法没有accepted的。 greedy才行。 longway
和peking2都给了代码。
true
★ 发自iPhone App: ChineseWeb 7.7
【在 f*******t 的大作中提到】
: 问过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++) {
|
f*******t
发帖数: 7549 | 10 贴出来看看？
longway
【在 c********t 的大作中提到】
: 恩，滚动二维数组用得好。考古发现dp解法没有accepted的。 greedy才行。 longway
: 和peking2都给了代码。
:
: true
: ★ 发自iPhone App: ChineseWeb 7.7
|
|
|
i**********e
发帖数: 1145 | 11 这里有贴dp AC 的代码。
你的转去 C++ 代码或许也 AC 了。
http://discuss.leetcode.com/questions/222/wildcard-matching
true
【在 f*******t 的大作中提到】
: 问过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++) {
|
p*****2
发帖数: 21240 | 12
这不fair吧。
【在 i**********e 的大作中提到】
: 这里有贴dp AC 的代码。
: 你的转去 C++ 代码或许也 AC 了。
: http://discuss.leetcode.com/questions/222/wildcard-matching
:
: true
|
f*******t
发帖数: 7549 | 13 改版那天我看到这个c++解法了，跟我的差不多。
【在 i**********e 的大作中提到】
: 这里有贴dp AC 的代码。
: 你的转去 C++ 代码或许也 AC 了。
: http://discuss.leetcode.com/questions/222/wildcard-matching
:
: true
|
c********t
发帖数: 5706 | 14 光贴代码，很难懂，你看看这个thread吧
http://www.mitbbs.com/article_t1/JobHunting/32258853_0_1.html
【在 f*******t 的大作中提到】
: 贴出来看看？
:
: longway
|
c********t
发帖数: 5706 | 15 二爷，新浪leetcode微博，是你的还是ihasleetcode的？
【在 p*****2 的大作中提到】
:
: 这不fair吧。
|
p*****2
发帖数: 21240 | 16
是我的。抢了leetcode的ID了。哈哈。
【在 c********t 的大作中提到】
: 二爷，新浪leetcode微博，是你的还是ihasleetcode的？
|
t**********h
发帖数: 2273 | 17 那上面的peking2的微博是leetcode抢了？
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
|
c********t
发帖数: 5706 | 18 二爷，greedy的解法时间复杂度是多少？我看好像worst case也是O(m*n)啊,为什么就
能过最大那个test case呢？
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
|
c********t
发帖数: 5706 | 19 小心苹果告三星
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
|
p*****2
发帖数: 21240 | 20
哪里又peking2的微薄？
【在 t**********h 的大作中提到】
: 那上面的peking2的微博是leetcode抢了？
|
|
|
p*****2
发帖数: 21240 | 21
苹果可以告三星，但是leetcode不会告peking2的。我有leetcode授权。
【在 c********t 的大作中提到】
: 小心苹果告三星
|
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | 23
感觉是test case的问题。没有包含worst case。按说这题DP应该也能过才对。感觉DP
比Greedy更有编程含量。Greedy有点凑出来的感觉。
【在 c********t 的大作中提到】
: 二爷，greedy的解法时间复杂度是多少？我看好像worst case也是O(m*n)啊,为什么就
: 能过最大那个test case呢？
|
c********t
发帖数: 5706 | 24 也许DP更有编程含量，但我觉得greedy更有思维含量。毕竟是O（1）的空间啊
DP
【在 p*****2 的大作中提到】
:
: 感觉是test case的问题。没有包含worst case。按说这题DP应该也能过才对。感觉DP
: 比Greedy更有编程含量。Greedy有点凑出来的感觉。
|
p*****2
发帖数: 21240 | 25
greedy面试并不常见。通常都很难证明。
【在 c********t 的大作中提到】
: 也许DP更有编程含量，但我觉得greedy更有思维含量。毕竟是O（1）的空间啊
:
: DP
|
