This is the solution about Leetcode-Regular Expression Matching.

Description

Implement regular expression matching with support for ‘.’ and ‘*’.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'.' 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

Analysis

Solution1

  1. Make use of Recursion.
  2. Each time compare first character of two strings, if the character of pattern is ‘.’ or equal to s. Then invoke this function recursively with the rest of p and s.
  3. Check if the scond character of p is ‘*’, if so, we need check if the character of s is equal to the pre character of p. If so, invoke this function recursively with the current p and suffix of s. If not, invoke this function recursively with the suffix of star in p and the current s.

Solution2

  1. Make use of DP
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
//Solution1:recursion
public class Solution1 {
public boolean isMatch1(String s, String p) {
if(p.length()==0) return s.length()==0;
if(p.length()==1) return (s.length()==1)&&(p.charAt(0)==s.charAt(0)||p.charAt(0)=='.');
if(p.charAt(1)!='*') {
if(s.length()==0) return false;
else return (s.charAt(0)==p.charAt(0)||p.charAt(0)=='.')&&isMatch(s.substring(1),p.substring(1));
}else {
while(s.length()>0 && (p.charAt(0)==s.charAt(0)||p.charAt(0)=='.')) {
if(isMatch(s,p.substring(2)))return true;
s = s.substring(1);
}
return isMatch(s,p.substring(2));
}
}
public boolean isMatch2(String s, String p) {
if(p.length() == 0) return s.length() == 0;
boolean firstMatch = s.length()!=0 && (s.charAt(0)==p.charAt(0) || p.charAt(0)=='.');
if(p.length()>=2 && p.charAt(1)=='*') {
return firstMatch && isMatch2(s.substring(1),p) || isMatch2(s, p.substring(2));
}
return firstMatch && isMatch2(s.substring(1), p.substring(1));
}
}
//Solution2:DP
public class Solution2 {
public boolean isMatch(String s, String p) {
if(s==null || p==null) return false;
//state: dp[i][j] represents first i characters of s and first p characters of p are matched or not.
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
//Initialize: dp[0][0] represents first 0 character of p and s must be matched.
dp[0][0] = true;
//dp[i][0] for i>0 are not matched
//dp[0][j], check if the second character of p is '*'
for(int i=0; i<p.length(); i++) {
if(p.charAt(i)=='*' && dp[0][i-1]) {
dp[0][i+1] = true;
}
}
//function:
for(int i=0; i<s.length(); i++) {
for(int j=0; j<p.length(); j++) {
if(s.charAt(i) == p.charAt(j)||p.charAt(j)=='.') {
dp[i+1][j+1] = dp[i][j];
}
else if(p.charAt(j)=='*') {
//eliminate j-1 and j -> j-2 should match i.
if(p.charAt(j-1)!= s.charAt(i) && p.charAt(j-1)!='.') {
dp[i+1][j+1] = dp[i+1][j-1];
}else {
// x* represent none x -> eliminate j-1 and j -> j-2 should match i -> dp[i+1][j-1]
// x* represent one x -> j-1 should match i -> dp[i+1][j]
// x* represent multiple x -> j should match i-1 -> dp[i][j+1]
dp[i+1][j+1] = (dp[i+1][j]||dp[i+1][j-1]||dp[i][j+1]);
}
}
}
}
return dp[s.length()][p.length()];
}
}