Wildcard Matching题求助# JobHunting - 待字闺中
c*t
1 楼
写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
isMatch("aab", "c*a*b") → false
isMatch（"mississippi", "m*si*"）竟然是true?
isMatch("aab", "c*a*b") → false
isMatch（"mississippi", "m*si*"）竟然是true?
a*x
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?
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
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可以参考下吗？
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
4 楼
楼主把这道题目和regular expression matching那题的意思混淆了吧。这个里面的“*
”和preceding character没有任何关系的。和regular expression matching不同的。
【在 c********t 的大作中提到】
: 写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
: isMatch("aab", "c*a*b") → false
: isMatch（"mississippi", "m*si*"）竟然是true?
”和preceding character没有任何关系的。和regular expression matching不同的。
【在 c********t 的大作中提到】
: 写完代码测试发现自己根本没读懂题，哪位大侠/侠女帮忙解释一下为什么
: isMatch("aab", "c*a*b") → false
: isMatch（"mississippi", "m*si*"）竟然是true?
c*t
5 楼
哦，是的。又土了。
“*
★ 发自iPhone App: ChineseWeb 7.7
【在 l**b 的大作中提到】
: 楼主把这道题目和regular expression matching那题的意思混淆了吧。这个里面的“*
: ”和preceding character没有任何关系的。和regular expression matching不同的。
“*
★ 发自iPhone App: ChineseWeb 7.7
【在 l**b 的大作中提到】
: 楼主把这道题目和regular expression matching那题的意思混淆了吧。这个里面的“*
: ”和preceding character没有任何关系的。和regular expression matching不同的。
c*t
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))
: ]
【在 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
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。
我有个优化的版本，但最后一个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
8 楼
这题greedy的很难写。等我总结到的时候再写吧。感觉面试DP就可以了。
c*t
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++) {
和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
10 楼
贴出来看看？
longway
【在 c********t 的大作中提到】
: 恩，滚动二维数组用得好。考古发现dp解法没有accepted的。 greedy才行。 longway
: 和peking2都给了代码。
:
: true
: ★ 发自iPhone App: ChineseWeb 7.7
longway
【在 c********t 的大作中提到】
: 恩，滚动二维数组用得好。考古发现dp解法没有accepted的。 greedy才行。 longway
: 和peking2都给了代码。
:
: true
: ★ 发自iPhone App: ChineseWeb 7.7
i*e
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++) {
你的转去 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
12 楼
这不fair吧。
【在 i**********e 的大作中提到】
: 这里有贴dp AC 的代码。
: 你的转去 C++ 代码或许也 AC 了。
: http://discuss.leetcode.com/questions/222/wildcard-matching
:
: true
f*t
13 楼
改版那天我看到这个c++解法了，跟我的差不多。
【在 i**********e 的大作中提到】
: 这里有贴dp AC 的代码。
: 你的转去 C++ 代码或许也 AC 了。
: http://discuss.leetcode.com/questions/222/wildcard-matching
:
: true
【在 i**********e 的大作中提到】
: 这里有贴dp AC 的代码。
: 你的转去 C++ 代码或许也 AC 了。
: http://discuss.leetcode.com/questions/222/wildcard-matching
:
: true
c*t
14 楼
光贴代码，很难懂，你看看这个thread吧
http://www.mitbbs.com/article_t1/JobHunting/32258853_0_1.html
【在 f*******t 的大作中提到】
: 贴出来看看？
:
: longway
http://www.mitbbs.com/article_t1/JobHunting/32258853_0_1.html
【在 f*******t 的大作中提到】
: 贴出来看看？
:
: longway
c*t
15 楼
二爷，新浪leetcode微博，是你的还是ihasleetcode的？
【在 p*****2 的大作中提到】
:
: 这不fair吧。
【在 p*****2 的大作中提到】
:
: 这不fair吧。
p*2
16 楼
是我的。抢了leetcode的ID了。哈哈。
【在 c********t 的大作中提到】
: 二爷，新浪leetcode微博，是你的还是ihasleetcode的？
t*h
17 楼
那上面的peking2的微博是leetcode抢了？
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
c*t
18 楼
二爷，greedy的解法时间复杂度是多少？我看好像worst case也是O(m*n)啊,为什么就
能过最大那个test case呢？
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
能过最大那个test case呢？
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
c*t
19 楼
小心苹果告三星
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
【在 p*****2 的大作中提到】
:
: 是我的。抢了leetcode的ID了。哈哈。
p*2
20 楼
哪里又peking2的微薄？
【在 t**********h 的大作中提到】
: 那上面的peking2的微博是leetcode抢了？
p*2
21 楼
苹果可以告三星，但是leetcode不会告peking2的。我有leetcode授权。
【在 c********t 的大作中提到】
: 小心苹果告三星
p*2
22 楼
p*2
23 楼
感觉是test case的问题。没有包含worst case。按说这题DP应该也能过才对。感觉DP
比Greedy更有编程含量。Greedy有点凑出来的感觉。
【在 c********t 的大作中提到】
: 二爷，greedy的解法时间复杂度是多少？我看好像worst case也是O(m*n)啊,为什么就
: 能过最大那个test case呢？
c*t
24 楼
也许DP更有编程含量，但我觉得greedy更有思维含量。毕竟是O（1）的空间啊
DP
【在 p*****2 的大作中提到】
:
: 感觉是test case的问题。没有包含worst case。按说这题DP应该也能过才对。感觉DP
: 比Greedy更有编程含量。Greedy有点凑出来的感觉。
DP
【在 p*****2 的大作中提到】
:
: 感觉是test case的问题。没有包含worst case。按说这题DP应该也能过才对。感觉DP
: 比Greedy更有编程含量。Greedy有点凑出来的感觉。
p*2
25 楼
greedy面试并不常见。通常都很难证明。
【在 c********t 的大作中提到】
: 也许DP更有编程含量，但我觉得greedy更有思维含量。毕竟是O（1）的空间啊
:
: DP
相关阅读
最近的感觉,也不知道该说啥, 随便说几句公司直接来offer Letter怎么工资谈判？请大家推荐绿卡申请律师问一道crack tech interview里面的题二面通过了,等offer,求祝福谁有编程之美的PDF完整版？【身心疲惫地最后一问】化学专业的还能找到提供H1B的工作吗？？下午A家第一次电面，求祝福忘记提老板的名字怎么办？大家 H1B transfer 都要些什么文件啊W2 contractor被裁后能拿失业金吗？什么样的语言学校可以先注册保住身份的工作经历和学历充水美国大公司查吗大概多久可以收到 I797 approval notice from USCIS？on-site之后amazon第一轮电面材料收到后多少天后 申请OPT加急合适？办H4的结婚证翻译件有没有有效期一说？CS 的各个公司的职位,都是到网站相应的career上去找么pre-OPT生效12个月以后OPT就作废了么