Regular Expression Matching
Description
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
简单的字符匹配
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
func isMatch(s string, p string) bool {
if len(s) == 0 && len(p) == 0 {
return true
} else if len(p) == 0 {
// p is empty but s
return false
}
matchChar := p[0]
if len(p) > 1 && p[1] == '*' {
// match any numbers of char(s)
// eat two char of p
p = p[2:]
for len(s) > 0{
if s[0] == matchChar || matchChar == '.' {
// try not to eat char of s
if isMatch(s, p) {
return true
}
// let's eat one char of s and try again
s = s[1:]
} else {
break
}
}
} else {
// match one char
// eat one char of p
p = p[1:]
// does it match?
if len(s) == 0 || (s[0] != matchChar && matchChar != '.') {
return false
}
// eat one char of s
s = s[1:]
}
return isMatch(s, p)
}
|
Similar Problem
20. Valid Parentheses
