t****a
发帖数: 1212 | 1 Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
Given two sets of strings A and B,
Problem 1:
to find out a wildcard pattern w. w can match all strings in A but none
string in B. it w doesn't exist, return false.
Problem 2:
to find a group of wildcard pattern W={w_i}, W can match all strings in A
but none string in B. Minimize the size of W. | b***m
发帖数: 5987 | | A*****i
发帖数: 3587 | | l***i
发帖数: 1309 | 4 problem 1 is easy, just make a DFA that recognizes only the strings in A,
and reject all other strings. Then your job is to wrong a regex to recognize
the same language as that DFA. Theoretically it is doable, although might
not be easy. | b***m
发帖数: 5987 | | m***k
发帖数: 946 | 6 这题很复杂
谁有好办法，我要好好学习一下
【在 t****a 的大作中提到】
: Implement wildcard pattern matching with support for '?' and '*'.
: '?' Matches any single character.
: '*' Matches any sequence of characters (including the empty sequence).
: The matching should cover the entire input string (not partial).
: Some examples:
: isMatch("aa","a") → false
: isMatch("aa","aa") → true
: isMatch("aaa","aa") → false
: isMatch("aa", "*") → true
: isMatch("aa", "a*") → true
| f*****e
发帖数: 2992 | 7 deterministic finite automata?
【在 b***m 的大作中提到】
: 神马是DFA呀？
| f*****e
发帖数: 2992 | 8 find,grep源码maybe works.
【在 m***k 的大作中提到】
: 这题很复杂
: 谁有好办法，我要好好学习一下
| k****r
发帖数: 807 | 9 目测的话，我想用recursive＋backtrack
分情况的, 我简单写了下，请指正
bool matchwords(char* word1, char* word2, int index1, int index2) {
if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
else {
if (word2[index2] == '*') {
if (matchwords(word1, word2, index1+1, index2+1)) return true;
else if (matchwords(word1, word2, index1+1, index2)) return true;
else if (word2[index2] == '?') {
return matchwords(word1, word2, index1+1, index2+1);
else {
if (word1[index1]== word2[index2] )
return matchwords(word1, word2, index1+1, index2+1);
else return false;
}
}
} | t****a
发帖数: 1212 | 10 这道题目和leetcode上的那题不同。请再看一遍题目？
另外，对leetcode的题目而言，你这个解法好像也不正确；同时，计算量也是指数的。
你确定这个解法通过了测试数据集得到正确结果了么？
true;
【在 k****r 的大作中提到】
: 目测的话，我想用recursive＋backtrack
: 分情况的, 我简单写了下，请指正
: bool matchwords(char* word1, char* word2, int index1, int index2) {
: if (index1 == strlen(word1)&& index2 == strlen(word2)) return true;
: else {
: if (word2[index2] == '*') {
: if (matchwords(word1, word2, index1+1, index2+1)) return true;
: else if (matchwords(word1, word2, index1+1, index2)) return true;
: else if (word2[index2] == '?') {
: return matchwords(word1, word2, index1+1, index2+1);
| | | k****r
发帖数: 807 | 11 哦，我又看了一遍，发现我只是在做ismatch 这个函数，
我的解法确实是指数级别的，没有考虑用dp做，
leetcode好久没做了，回头看看去：）
【在 t****a 的大作中提到】
: 这道题目和leetcode上的那题不同。请再看一遍题目？
: 另外，对leetcode的题目而言，你这个解法好像也不正确；同时，计算量也是指数的。
: 你确定这个解法通过了测试数据集得到正确结果了么？
:
: true;
| t****a
发帖数: 1212 | | F********9
发帖数: 44 | 13 bool isMatch(const char *content, const char *pattern) {
if(content == NULL) {
if(pattern == NULL) {
return true;
} else {
return false;
}
}
if(*pattern == '*' && *(pattern+1) == '\0') { // *
return true;
} else if(*content == '\0') {
if(*pattern == '\0') {
return true;
} else {
return false;
}
} else if(*pattern == '?') { //?
if(*(pattern+1) == '*') { //?*
pattern += 2;
while(*content != '\0') {
while(*content != *pattern) {
++content;
}
if(isMatch(content, pattern)) {
return true;
} else { // skip failed match, move on
++content;
continue;
}
}
} else {
return isMatch(content+1, pattern+1);
}
} else if(*content ==*pattern) { // char = char
if(*(pattern+1) == '*') {
while(*content == *pattern) {
++content;
}
return isMatch(content, pattern+2);
} else {
return isMatch(content+1, pattern+1);
}
}
return false;
} | t****a
发帖数: 1212 | | c********t
发帖数: 5706 | 15 与leetcode regular expression matching那题思路不一样吗？
【在 t****a 的大作中提到】
: Implement wildcard pattern matching with support for '?' and '*'.
: '?' Matches any single character.
: '*' Matches any sequence of characters (including the empty sequence).
: The matching should cover the entire input string (not partial).
: Some examples:
: isMatch("aa","a") → false
: isMatch("aa","aa") → true
: isMatch("aaa","aa") → false
: isMatch("aa", "*") → true
: isMatch("aa", "a*") → true
| t****a
发帖数: 1212 | 16 和那个题目不一样啊，难点在下面的Problem1和Problem2
【在 c********t 的大作中提到】
: 与leetcode regular expression matching那题思路不一样吗？
| b*2
发帖数: 94 | 17 去年还真做过这道题：
private static boolean match(String regEx, String word) {
// TODO Auto-generated method stub
if(regEx == "*")
return true;
int reIndex = 0;
int wdIndex = 0;
for(;reIndex
if(regEx.charAt(reIndex)==word.charAt(wdIndex)){
continue;
}else if(regEx.charAt(reIndex)!='?'&®Ex.charAt(reIndex)!='*'){
//simply not equivalent
return false;
}else if(regEx.charAt(reIndex)=='?'){
//deal with ?
//goto the next char
continue;
}else{
//deal with *
if(reIndex+1==regEx.length()) {
//this * is the very last one
return true;
}
boolean flag = false;
for(int i=0; wdIndex+i
int j=0;
//check whether the following is * also
for(; reIndex+j
if(regEx.charAt(reIndex+j)!='*') {
break;
}
}
if(reIndex+j==regEx.length()){
//this if checks whether it is like "abc***"
return true;
}else{
if(regEx.charAt(reIndex+j) == word.charAt(wdIndex+i)
|| regEx.charAt(reIndex+j) == '?'){
flag = flag||match(regEx.substring(reIndex+j),word.substring(wdIndex+
i));
}
}
}
return flag;
}
}
if(reIndex==regEx.length()&&wdIndex==word.length())
return true;
else
return false;
} | b*2
发帖数: 94 | 18 当时的全部测试：
match("*","abc") //true
match("*c","abc") //true
match("*a","abc") //false
match("a*","abc") //true
match("a?","abc") //false
match("ab?","abc") //true
match("a?c","abc") //true
match("*bc","abcbc") //true
match("a*b*c","abc") //true
match("*","") //true
match("*a","bac") //false
match("a*b","ab") //true
match("a?b","ab") //false
match("a**bc","acbc") //true
match("a*?bc","abc") //false
match("a**?**?bc","acbc") //false
match("a**?**?bc","accbc") //true |
|
