S*******C
发帖数: 822 | 1 pattern match的题
// Text: a-z, A-Z, 0-9
// Pattern: a-z, A-z, 0-9, +, *
// + = 1 or more times
// * = 0 or more times. [email protected]/* */ 3 acres
//
// Pattern: a+b
// Text: aab, b return true-google 1point3acres
//
// Pattern: a+b*
// Text: aab, aa return true | I**********s
发帖数: 441 | 2 a+b应该不match b吧？
代码如下：
bool match(const char * s, const char * p) {
if (! *p) return ! *s;
if (*(p + 1) == '*') {
// match(s+1, p) - match next char in s.
// match(s, p+2) - match exactly nothing in s.
if (*p == *s) return match(s+1, p) || match(s, p+2);
else return match(s, p+2); // matche exactly nothing in s.
}
else if (*(p + 1) == '+') {
// match(s+1, p) - match next char in s.
// match(s+1, p+2) - match exactly 1 char in s.
if (*p == *s) return match(s+1, p) || match(s+1, p+2);
else return false;
}
else if (*p == *s) {
return match(s+1, p+1); // match exactly 1 char in s.
}
else {
return false;
}
}
【在 S*******C 的大作中提到】
: pattern match的题
: // Text: a-z, A-Z, 0-9
: // Pattern: a-z, A-z, 0-9, +, *
: // + = 1 or more times
: // * = 0 or more times. [email protected]/* */ 3 acres
: //
: // Pattern: a+b
: // Text: aab, b return true-google 1point3acres
: //
: // Pattern: a+b*
| S*******C
发帖数: 822 | 3 a+b不match b，但很多test case通不过，看看怎么回事
public class Solution {
public boolean match(String s, String p) {
return match(s, 0, p, 0);
}
private boolean match(String s, int i, String p, int j) {
if (j >= p.length() - 1) {
return i >= s.length() - 1;
} else if (i >= s.length() - 1) {
return j >= p.length() - 1;
}
if (p.charAt(j + 1) == '*') {
// match(s+1, p) - match next char in s.
// match(s, p+2) - match exactly nothing in s.
if (s.charAt(i) == p.charAt(j))
return match(s, i + 1, p, j) || match(s, i, p, j + 2);
else
return match(s, i, p, j + 2); // matches exactly nothing in
s.
} else if (p.charAt(j + 1) == '+') {
// match(s+1, p) - match next char in s.
// match(s+1, p+2) - match exactly 1 char in s.
if (s.charAt(i) == p.charAt(j))
return match(s, i + 1, p, j) || match(s, i + 1, p, j + 2);
else
return false;
} else if (s.charAt(i) == p.charAt(j)) {
return match(s, i + 1, p, j + 1); // match exactly 1 char in s.
} else {
return false;
}
}
public static void main(String args[]) {
test("aab", "a+b");//true
test("aab", "aab");//true
test("aab", "aa*b");//true
test("aab", "a+b*");//true
test("aab", "aa+b");//true
test("aab", "a+b+");//true
test("aab", "a+b*");//true
test("aab", "aaa+b");//false
test("aab", "a+bb+");//false
}
static void test(String s, String p) {
System.out.println(sol.match(s, p));
}
static Solution sol = new Solution();
}
【在 I**********s 的大作中提到】
: a+b应该不match b吧？
: 代码如下：
: bool match(const char * s, const char * p) {
: if (! *p) return ! *s;
: if (*(p + 1) == '*') {
: // match(s+1, p) - match next char in s.
: // match(s, p+2) - match exactly nothing in s.
: if (*p == *s) return match(s+1, p) || match(s, p+2);
: else return match(s, p+2); // matche exactly nothing in s.
: }
| I**********s
发帖数: 441 | 4 这涉及到C++转换成Java的一点小技巧。这样改就可以都通过了：
private boolean match(String s, int i, String p, int j) {
if (j == p.length()) return i == s.length();
if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
// match(s+1, p) - match next char in s.
// match(s, p+2) - match exactly nothing in s.
if (i < s.length() && s.charAt(i) == p.charAt(j))
return match(s, i + 1, p, j) || match(s, i, p, j + 2);
else
return match(s, i, p, j + 2); // matches exactly nothing in
s.
} else if (j + 1 < p.length() && p.charAt(j + 1) == '+') {
// match(s+1, p) - match next char in s.
// match(s+1, p+2) - match exactly 1 char in s.
if (i < s.length() && s.charAt(i) == p.charAt(j))
return match(s, i + 1, p, j) || match(s, i + 1, p, j + 2);
else
return false;
} else if (i < s.length() && s.charAt(i) == p.charAt(j)) {
return match(s, i + 1, p, j + 1); // match exactly 1 char in s.
} else {
return false;
}
} | S*******C
发帖数: 822 | 5 谢谢，你真牛啊
in
【在 I**********s 的大作中提到】
: 这涉及到C++转换成Java的一点小技巧。这样改就可以都通过了：
: private boolean match(String s, int i, String p, int j) {
: if (j == p.length()) return i == s.length();
: if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
: // match(s+1, p) - match next char in s.
: // match(s, p+2) - match exactly nothing in s.
: if (i < s.length() && s.charAt(i) == p.charAt(j))
: return match(s, i + 1, p, j) || match(s, i, p, j + 2);
: else
: return match(s, i, p, j + 2); // matches exactly nothing in
| I**********s
发帖数: 441 | |
|
