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
相关阅读
Google内部推荐定好的电面时间还没到，公司就把job post删了，什么情况？请教:OPT期间H1B已经approve出境(automatic revalidation)口头offer处理了一个月还没结果，怎么回事？H1B transfer可以两家公司一块办理吗求助啊 我是不被C1的HR 給黑了拿到H1B以后，activate status有时间要求吗请问自己投的完的话是不是就不能找refer了求个opt挂靠的办法一个月没做题，手生的想钻地洞。求推荐intern 2013 cs master有 cracking the code interview的答案吗纽约7万5能活吗opt到h1b如何换驾照请大家帮我分析一下大家都是在什么网站做题的呢？Amazon TRMS is hiring a research scientist求解答：曾经的H1B名额能用吗？google电面一周了找一个stream of double 的exact median怎么做？