Implement regular expression matching with support for '.'
and '*'
.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
思路:
参考自:http://www.tuicool.com/articles/Ebiymu
1 public boolean isMatch(String s, String p) {
2 // base case
3 if (p.length() == 0) {
4 return s.length() == 0;
5 }
6
7 // special case
8 if (p.length() == 1) {
9 // if the length of s is 0, return false
10 if (s.length() < 1) {
11 return false;
12 }
13 //if the first does not match, return false
14 else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
15 return false;
16 }
17
18 // otherwise, compare the rest of the string of s and p.
19 else {
20 return isMatch(s.substring(1), p.substring(1));
21 }
22 }
23
24 // case 1: when the second char of p is not '*'
25 if (p.charAt(1) != '*') {
26 if (s.length() < 1) {
27 return false;
28 }
29 if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
30 return false;
31 } else {
32 return isMatch(s.substring(1), p.substring(1));
33 }
34 }
35
36 // case 2: when the second char of p is '*', complex case.
37 else {
38 //case 2.1: a char & '*' can stand for 0 element
39 if (isMatch(s, p.substring(2))) {
40 return true;
41 }
42
43 //case 2.2: a char & '*' can stand for 1 or more preceding element,
44 //so try every sub string
45 int i = 0;
46 while (i<s.length() && (s.charAt(i)==p.charAt(0) || p.charAt(0)=='.')){
47 if (isMatch(s.substring(i + 1), p.substring(2))) {
48 return true;
49 }
50 i++;
51 }
52 return false;
53 }
54 }