正则表达式匹配

实现支持'.'和'*'的正则表达式匹配。

'.'匹配任意一个字母。

'*'匹配零个或者多个前面的元素。

匹配应该覆盖整个输入字符串，而不仅仅是一部分。

需要实现的函数是：bool isMatch(const char *s, const char *p)

思路：
假设s(0,i)为s由下标0到i的字符串
假设p(0,j)为s由下标0到j的字符串

dp[i][j]为Bool类型,表示字符串s(0,i-1)是否能匹配正则表达式p(0,j-1)

• 第一种情况
  if s[i-1] = p[j-1]
  dp[i][j] = dp[i-1][j-1]
• 第二种情况
  if p[j-1] == '.'
  dp[i][j] = dp[i-1][j-1]
• 第三种
  if p[j-1] == '*'

1. 如果 p[j-2] != s[i-1] && s[i-1] != '.'
   dp[i][j] = dp[i][j-2] a*为空
2. 如果 p[j-2] == s[i-1] || s[i-1] == '.'
   dp[i][j] = dp[i][j-1] a*为a
   或者dp[i][j] = dp[i][j-1] a*匹配多个a
   或者dp[i][j] = dp[i][j-2] a*为空

class Solution {
public:
    /**
     * @param s: A string 
     * @param p: A string includes "." and "*"
     * @return: A boolean
     */
    bool isMatch(const char *s, const char *p) {
        // write your code here
        if (p==NULL || s == NULL) {
            return false;
        }
        if (p[0] == '*') {
            return false;
        }
        int sLength = strlen(s);
        int pLength = strlen(p);
        vector<vector<bool>> dp(sLength+1,vector<bool>(pLength+1,false));
        dp[0][0] = true;
 /*          a * b b
           0 1 2 3 4 
       0   T F T F F   
     b 1     F F T
     b 2       F F T
 */
       for(int j = 1; j < pLength + 1; j++) {
            if (p[j-1] == '*') {
                if (dp[0][j-1] || (j > 1 && dp[0][j-2] == true)) {
                    dp[0][j] = true;
                }
            }
        }
        
        for(int i = 1; i <= sLength; i++) {
            for(int j = 1;j <= pLength; j++) {
                if (s[i-1]==p[j-1]) {
                    dp[i][j] = dp[i-1][j-1];
                } else if (p[j-1] == '.') {
                    dp[i][j] = dp[i-1][j-1];
                } else if (p[j-1] == '*') {
                    if(p[j-2] != s[i-1] && p[j-2] != '.') {
                        dp[i][j] = dp[i][j-2];
                    } else {
                        dp[i][j] = dp[i-1][j] || dp[i][j-1] || dp[i][j-2];
                    }
                }
            }
        }
        return dp[sLength][pLength];
    }
};