leetcode 10.正则表达式

#include <iostream>
#include <vector>
#include <functional>
using namespace std;
class Solution
{
public:
    bool isMatch(string &s, string &p)
    {
        int sSize = s.size();
        int pSize = p.size();
        vector<vector<int>> a(sSize + 1, vector(pSize + 1, 0));
        a[0][0] = 1;
        function<bool(int, int)> match = [&](int n, int m) {
            if (n < 0 || m < 0)
                return false;
            if (a[n][m] == 1)
                return true;
            if (a[n][m] == -1)
                return false;
            if (n > 0 && m > 0)
            {
                if (s[n - 1] == p[m - 1] || p[m - 1] == '.')
                    if (match(n - 1, m - 1))
                    {
                        a[n][m]=1;
                        return true;
                    }
            }
            if (m > 1)
            {
                if (p[m - 1] == '*')
                {
                    if (n > 0)
                    {
                        if (s[n - 1] == p[m - 2] || p[m - 2] == '.')
                            if (match(n - 1, m))
                                {
                        a[n][m]=1;
                        return true;
                    }
                    }
                    if (match(n, m - 2))
                        {
                        a[n][m]=1;
                        return true;
                    }
                }
            }
            a[n][m]=-1;
            return false;
        };
        return match(sSize, pSize);
    }
};

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注