LeetCode 10. Regular Expression Matching

Regular Expression Matching | LeetCode OJ
https://leetcode.com/problems/regular-expression-matching/

这个问题的关键需要对pattern里各种字符的情况逐个讨论清楚。

以动态规划的解法为例。假设s长度为m，p长度为n，需要一个m*n的二维数组保存P和S匹配的情况（实际上2*n的数组应该就够了，但为了简化讨论，采用m*n的数组）。

注意数组A[i][j]实际表示的是p[j-1]和s[i-1]的匹配情况，因为我们需要A[0][0]来表示s和p为空的情况。

当s和p都为空，匹配是成功的，所以A[0][0] = true。

当s不为空，p为空，匹配肯定是失败的，所以A[1..i][0] = false。

当s为空，p不为空，如果p为"a*b*c*..."的形式，则可以匹配成功。所以当p[j-1]为'*'时，只要之前的匹配成功了，p[j-1]就可以匹配成功，因为'*'此时表示0个字串，所以p[j-2]值为多少并不重要。因此:

if(j>1 && p[j-1] == '*'){
    A[0][j] = A[0][j-2];   
}

当p[j-1]为'.'，只要前续匹配成功，当前匹配就一定会成功，所以:

A[i][j] = A[i-1][j-1]

当p[j-1]为普通字符，如果前续匹配成功且p[j-1] == s[i-1]，则匹配成功。

当p[j-1]为'*'，有几种情况：

a. 不匹配任何字符，此时匹配是否成功取决于p往前两个字符的匹配是否成功，即 A[i][j] = A[i][j-2]。

b. 匹配1个字符，此时匹配是否成功取决于p往前一个字符是否匹配成功，即 A[i][j] = A[i][j-1]。

c. 匹配>1个字符。此时匹配是否成功取决于当前"x*"是否匹配s[1...i-2]成功，且当前字符s[i-1]符合匹配，即A[i][j] = A[i][j-1] && (p[j-1] == s[i-1] || p[j-1] == '.')。

具体可以用几个例子画个矩阵跑一下：

s="aaaa", p = "a*a*"

	null	a	*	a	*
null	T	F	T	F	T
a	F	T	T	T	T
a	F	F	T	T	T
a	F	F	T	T	T
a	F	F	T	T	T

s="aaaa", p = "a*aa"

	null	a	*	a	a
null	T	F	T	F	F
a	F	T	T	T	F
a	F	F	T	T	T
a	F	F	T	T	T
a	F	F	T	T	T

代码如下：

 1 #include "stdafx.h"
 2 using namespace std;
 3 /* "baa", "aa" : ".*aa"
 4 "a" : "a*a*"
 5 "a", "ab" : "a*c*" 
 6 "a" : "c*a*" */
 7 class LC010_Regular_Expression_Matching{
 8 public:
 9     bool isMatch(string s, string p) {
10         int m = s.size(), n = p.size();
11         vector<vector<bool>> mem(2, vector<bool>(n+1,false));
12         mem[0][0] = true;
13         for(int j = 2; j <= n; j++){
14             if(p[j-1] == '*'){
15                 mem[0][j] = mem[0][j-2];
16             }
17         }
18         
19         int cur = 0, prev = 0;
20         for(int i = 1; i <= m; i++){
21             cur = i%2;
22             prev = (i-1)%2;
23             mem[cur][0] = false;
24             for(int j = 1; j <= n; j++){
25                 if(p[j-1] == '.'){
26                     mem[cur][j] = mem[prev][j-1];
27                 }else if(p[j-1] == '*'){
28                     bool isMatch = mem[cur][j-2] || mem[cur][j-1];
29                     if(!isMatch){
30                         isMatch = mem[prev][j] && (p[j-2] == s[i-1] || p[j-2] == '.');
31                     }
32                     mem[cur][j] = isMatch;
33                 }else{
34                     mem[cur][j] = mem[prev][j-1] && p[j-1] == s[i-1];
35                 }
36             }
37         }
38         
39         return mem[cur][n];
40     }
41 };