leetcode 10. 正则表达式匹配  hard

题目描述：

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

 
示例 1：

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

解题思路：

dp  看题解吧

代码：

class Solution {
public:
    bool isMatch(string s, string p) {

        int len_s = s.size();
        int len_p = p.size();

        // 初始化 dp 数组， 默认dp[i][0] 初始化为false：对应s非空， p空串的情况
        vector<vector<bool>> dp(len_s+1, vector<bool>(len_p+1, false));
        dp[0][0] = true;
        for (int j=2; j <= len_p; j+=2)
        {
            dp[0][j] = dp[0][j-2] && (p[j-1] == '*');
        }

        for (int i = 1; i<=len_s; i++)
        {
            for (int j = 1; j<=len_p; j++)
            {
                if (p[j-1] == '*')
                {
                    if (j >= 2)
                        dp[i][j] = (dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')) || dp[i][j-2];
                }
                else if (p[j-1] == '.')
                {
                    dp[i][j] = dp[i-1][j-1];
                }
                else
                {
                    dp[i][j] = (s[i-1] == p[j-1]) && dp[i-1][j-1];
                }
            }
        }

        return dp[len_s][len_p];
    }
};

---