LeetCode-Regular Expression Matching

前端之家收集整理的这篇文章主要介绍了LeetCode-Regular Expression Matching前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

这里写链接内容
这里写链接内容
这个是处理正则表达式的题目
核心问题是*的意思表示它前一位的重复次数可以为0
对于这类匹配 定义一个二维的DP数组,其中dp[i][j]表示s[0,i)和p[0,j)是否match,然后有下面三种情况

  1. P[i][j] = P[i - 1][j - 1],if p[j - 1] != ‘*’ && (s[i - 1] == p[j - 1] || p[j - 1] == ‘.’);
  2. P[i][j] = P[i][j - 2],if p[j - 1] == ‘*’ and the pattern repeats for 0 times;
  3. P[i][j] = P[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == ‘.’),if p[j - 1] == ‘*’ and the pattern repeats for at least 1 times.
class Solution
{
public:
    static const int FRONT=-1;
    bool isMatch(string s,string p)
    {
        int m = s.length(),n = p.length();
        bool dp[m+1][n+1];
        dp[0][0] = true;
//初始化第0行,除了[0][0]全为false,毋庸置疑,因为空串p只能匹配空串,其他都无能匹配
        for (int i = 1; i <= m; i++)
            dp[i][0] = false;
//初始化第0列,只有X*能匹配空串,如果有*,它的真值一定和p[0][j-2]的相同(略过它之前的符号)
        for (int j = 1; j <= n; j++)
            dp[0][j] = j > 1 && '*' == p[j - 1] && dp[0][j - 2];

        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (p[j - 1] == '*')
                {
                    dp[i][j] = dp[i][j - 2] || (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j];

                }
                else   //只有当前字符完全匹配,才有资格传递dp[i-1][j-1] 真值
                {
                    dp[i][j] = (p[j - 1] == '.' || s[i - 1] == p[j - 1]) && dp[i - 1][j - 1];

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

猜你在找的正则表达式相关文章