题目链接：Regular Expression Matching

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

这道题的要求是判断字符串s能否和正则表达式p相匹配。其中‘.‘匹配任意单个字符，‘*‘匹配0个或多个‘*‘的前一字符。如果匹配能整个串返回true。

1. 回溯暴力匹配

思路是进行递归回溯匹配。当p的下一个字符是‘*‘的时候，则循环检测p与s的当前字符是否匹配（每次s后移1位，直到结束或者不匹配）；当p的下一个字符不是‘*‘的时候，直接检测字符串是否结束或者p与s的当前字符是否匹配。注意‘.‘可以与任意单个字符匹配。

时间复杂度：???

空间复杂度：O(1)

 1 class Solution
 2 {
 3 public:
 4     bool isMatch(const char *s, const char *p)
 5     {
 6         if(*p == ‘\0‘ )
 7             return *s == ‘\0‘;
 8         
 9         if(*(p + 1) == ‘*‘)
10         {
11             while(*s != ‘\0‘ && (*p == ‘.‘ || *s == *p))
12             {
13                 if(isMatch(s, p + 2))
14                     return true;
15                 ++ s;
16             }
17             return isMatch(s, p + 2);
18         }
19         else if(*s != ‘\0‘ && (*p == ‘.‘ || *s == *p))
20             return isMatch(s + 1, p + 1);
21         
22         return false;
23     }
24 };

2. 动态规划

思路是使用bool类型的二维数组dp[m+1][n+1]（m、n分别为字符串s和p的长度）记录s和p是否匹配，即dp[i+1][j+1]表示s的前i个字符是否与p的前j的字符相匹配。

如果p[j]不等于‘*‘，则dp[i + 1][j + 1] = dp[i][j] && s[i] == p[j]

如果p[j]等于‘*‘，则当且仅当在下面三种情况为真，dp[i + 1][j + 1]为真：

‘*‘前面字符重复出现0次，则p字符串需要往前看2位，即dp[i + 1][j - 1]是否为真
‘*‘前面的字符重复出现1次，则p字符串只需要往前看1位，即dp[i + 1][j]是否为真
‘*‘前面的字符重复出现次数大于1次，则s字符串需要往前看1位，即dp[i][j + 1]是否为真，以及s字符串当前字符（s[i]）与p字符串‘*‘前面字符（p[j - 1]）是否相匹配。

注意，‘.‘可以与任意单个字符匹配。

注：动态规划思路是参考的这里。这里将空间复杂度降低到了O(n)，有兴趣的可以看看。

时间复杂度：O(mn)

空间复杂度：O(mn)

 1 class Solution
 2 {
 3 public:
 4     bool isMatch(const char *s, const char *p)
 5     {
 6         int m = strlen(s), n = strlen(p);
 7         bool dp[m + 1][n + 1];
 8         
 9         dp[0][0] = true;
10         for(int i = 0; i < m; ++ i)
11             dp[i + 1][0] = false;
12         for(int j = 0; j < n; ++ j)
13             dp[0][j + 1] = ‘*‘ == p[j] && dp[0][j - 1];
14         
15         for(int i = 0; i < m; ++ i)
16             for(int j = 0; j < n; ++ j)
17             {
18                 if(p[j] != ‘*‘)
19                     dp[i + 1][j + 1] = dp[i][j] && (‘.‘ == p[j] || s[i] == p[j]);
20                 else
21                     dp[i + 1][j + 1] = dp[i + 1][j - 1] || dp[i + 1][j] || 
22                         dp[i][j + 1] && (‘.‘ == p[j - 1] || s[i] == p[j - 1]);
23             }
24         
25         return dp[m][n];
26     }
27 };

LeetCode --- 10. Regular Expression Matching

1. 回溯暴力匹配

2. 动态规划