Leetcode
Dynamic Programming
10 Regular Expression Matching

1. Question

Implement regular expression matching with support for'.'and'*'.
1
'.' Matches any single character.
2
'*' Matches zero or more of the preceding element.
3
4
The matching should cover the
5
entire
6
input string (not partial).
7
8
The function prototype should be:
9
bool isMatch(const char *s, const char *p)
10
11
Some examples:
12
isMatch("aa","a") → false
13
isMatch("aa","aa") → true
14
isMatch("aaa","aa") → false
15
isMatch("aa", "a*") → true
16
isMatch("aa", ".*") → true
17
isMatch("ab", ".*") → true
18
isMatch("aab", "c*a*b") → true
Copied!

2. Implementation

(1) Recursion
思路: 我们从后往前匹配,这样的方法好处是一旦我们遇到"*",由于*的在这里的特性是匹配前一个字符0至多次,这样的话我们只要检查*前的一个字符是否和当前p的字符相同即可。在从后往前匹配的过程中,我们将过程分成几个cases:
1.如果pIndex = -1时,说明我们已经匹配完p的所有字符,这时只有当sIndex也等于-1时我们才return true
2.如果p.charAt(pIndex) = ‘*’时
1
class Solution {
2
public boolean isMatch(String s, String p) {
3
return isMatch(s, s.length() - 1, p, p.length() - 1);
4
}
5
6
public boolean isMatch(String s, int sIndex, String p, int pIndex) {
7
if (pIndex == -1) {
8
return sIndex == -1;
9
}
10
if (p.charAt(pIndex) == '*') {
11
if (sIndex >= 0 && (p.charAt(pIndex - 1) == '.' || p.charAt(pIndex - 1) == s.charAt(sIndex))) {
12
if (isMatch(s, sIndex - 1, p, pIndex)) {
13
return true;
14
}
15
}
16
return isMatch(s, sIndex, p, pIndex - 2);
17
}
18
19
if (sIndex >= 0 && (p.charAt(pIndex) == '.' || s.charAt(sIndex) == p.charAt(pIndex))) {
20
return isMatch(s, sIndex - 1, p, pIndex - 1);
21
}
22
23
return false;
24
}
25
}
Copied!
(2) DP
1
Copied!

3. Time & Space Complexity