正则表达式匹配

题目描述：

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

• '.' 匹配任意单个字符
• '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s 和 p的，而不是部分字符串（我是说p有尾巴的话一定要尾部也对应，不可以中间截止）。

class Solution {
public:

    bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));

    //假装前面有负数部分，然后我们给了一个中间的结果，到这里已经为止是true
    dp[0][0] = true;

    //因为-1可能导致负数，所以我们从1开始，但是1要用0这个部分进行迭代，所以我们先把0这个部分处理了
	//已经让(0, 0)为true了，0这一层的j需要为true的只有不要*以及它之前的那一位的情况，取决于它再前面一位
	//j为0而i不为0，前面根本就没有匹配，不需要true，所以不用处理
    for (int j = 2; j <= n; j += 2) {
        if (p[j - 1] == '*') {
            dp[0][j] = dp[0][j - 2];
        }
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p[j - 1] == s[i - 1] || p[j - 1] == '.') {
                //如果它们本身就匹配
                dp[i][j] = dp[i - 1][j - 1];
            } else if (p[j - 1] == '*') {//如果这一位是'*'，那么为了后面的递归，我们需要用前面的结果代替它
              //只能从这两个位置来  
			  dp[i][j] = dp[i][j - 2];  //用前两格的位置的情况代替，如果是第一次到这个位置（0次）
                //不匹配的i只能到'*'后面去碰碰运气了
                if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
                    dp[i][j] = dp[i][j] || dp[i - 1][j];
                }
            }
        }
    }

    return dp[m][n];
}
};

可以直接当作大模拟来做，但是这样压栈太多，在leetcode上过不了，于是考虑用dp数组来模仿。

动态规划的精髓在于怎么从小到大，哪些边界条件。

这道题就是要想到在首次匹配以外的位置应该当作已经处理成功来看，这样才能利用原有的成功。

时间复杂度和空间复杂度都是O(mn)。

下面是大模拟方法，分类更多，因为方向不同考虑的情况不一样。

#include <iostream>
#include <string>
using namespace std;

bool matchCore(string str, string pattern, int poss, int posp)
{
    if (poss == str.length() && posp == pattern.length())
        return true;

    if (posp == pattern.length())
        return false;

    // 如果 pattern 的下一个字符是 '*'
    if (posp + 1 < pattern.length() && pattern[posp + 1] == '*')
    {
        if (poss < str.length() &&
            (str[poss] == pattern[posp] || pattern[posp] == '.'))
        {
            return matchCore(str, pattern, poss, posp + 2) ||
                   matchCore(str, pattern, poss + 1, posp);
        }
        return matchCore(str, pattern, poss, posp + 2);
    }

    // 普通匹配
    if (poss < str.length() &&
        (str[poss] == pattern[posp] || pattern[posp] == '.'))
    {
        return matchCore(str, pattern, poss + 1, posp + 1);
    }

    return false;
}
bool isMatch(string s, string p)
{
    if (s.empty() || p.empty())
        return false;
    return matchCore(s, p, 0, 0);
}

int main()
{
    string a = "aaaaabaccbbccababa";
    string b = "a*b*.*c*c*.*.*.*c";
    if (isMatch(a, b))
        cout << "true";
    else
        cout << "false";
}