算法题解:实现正则表达式 '.' 和 '*' 的匹配(动态规划)

前端之家收集整理的这篇文章主要介绍了算法题解:实现正则表达式 '.' 和 '*' 的匹配(动态规划)前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目分析

@H_502_2@题目链接10. Regular Expression Matching

@H_502_2@我们需要回答这么一个问题:模式p(正则表达式)是否匹配字符串s

@H_502_2@经过思考,难点主要在于*究竟应该匹配多少个字符
因为*并不是匹配越多字符越好(不能贪婪匹配)
比如模式a*abc中的a*只能匹配aaabcaa。如果a*匹配了aaa,那么剩余的模式abca*abc减去开头的a*)就无法匹配剩余的字符串'bc'。换一种说法,如果a*匹配3个a,a*a(4个a)无法匹配aaabc的任何前缀。
同理,如果匹配的字符少了,也会导致模式无法匹配字符串
还是上面这个例子,如果a*abc中的a*只匹配a,那么剩余的模式abc就无法匹配剩余的字符串'aabc'。换一种说法,如果a*只匹配1个a,a*ab(aab)无法匹配aaabc的任何前缀。

@H_502_2@动态规划要求:从最简单的子问题出发,利用已知的子问题的答案,得到更复杂的子问题的答案,循环往复,最终得到祖先问题的答案。

@H_502_2@假设有字符串s0s1s2...sx模式p0p1p2...py(其中pn代表一个子模式,也就是字符以及它后面的*):

@H_403_74@
  • @H_502_2@如果py不是*匹配,那么字符串s0s1s2...sx匹配模式p0p1p2...py当且仅当:

    @H_403_74@
  • @H_502_2@sx == py指定的字符 && s0s1s2...sx-1匹配p0p1p2...py-1

  • @H_502_2@如果py是*匹配,那么字符串s0s1s2...sx匹配模式p0p1p2...py当且仅当:

    @H_403_74@
  • @H_502_2@s0s1s2...sx匹配p0p1p2...py-1,也就是说去掉py以后字符串依然与模式匹配。此时py匹配0个字符。

  • @H_502_2@或 sx == py指定的字符 && s0s1s2...sx-1匹配p0p1p2...py,也就是说去掉sx以后字符串依然与模式匹配。此时py匹配1个或多个字符。

  • @H_502_2@我们用二维数组match来存储已经解出的子问题答案。match[x][y]表示s0s1s2...sx-1是否匹配p的的p0p1p2...py-1。特别地,x=0时表示字符串是空串,y=0时表示模式是空模式。

    代码实现

    class Solution
    {
      public:
        bool isMatch(string s,string p)
        {
            vector<vector<bool>> match(s.size() + 1,vector<bool>(p.size() + 1,false));
            // match[x][y]表示s0s1s2...sx-1是否匹配p的的p0p1p2...py-1。特别地,x=0时表示字符串是空串,y=0时表示模式是空模式。
            match[0][0] = true; // 空串与空模式匹配
    
            int j = 1,lastPatternIndex = 0; // lastPatternIndex存储了上一个子模式的下标
            char currentPatternChar = 0;     // 当前子模式需要匹配的字符
            bool isMulti = false;            // 当前子模式是不是*匹配
    
            while (j <= p.size())
            {
                isMulti = false; // isMulti默认为false
                // j是当前子模式在p中的下标
                // 获取当前子模式的信息
                currentPatternChar = p[j - 1];
                while (j < p.size() && p[j] == '*')
                { // 将当前子模式的*跳过
                    isMulti = true;
                    ++j;
                }
    
                // i是s当前检测到的字符的下标
                for (int i = 0; i <= s.size(); ++i)
                {
                    if (!isMulti)
                    {
                        // 非*匹配
                        // s0s1s2...sx-1匹配p0p1p2...py-1
                        // && sx == py指定的字符(至少需要一个字符)
                        match[i][j] = i >= 1 && match[i - 1][lastPatternIndex] && (currentPatternChar == '.' || s[i - 1] == currentPatternChar);
                    }
                    else
                    {
                        // *匹配
                        // s0s1s2...sx匹配p0p1p2...py-1
                        // || (sx == py指定的字符(至少需要一个字符) && s0s1s2...sx-1匹配p0p1p2...py)
                        match[i][j] = match[i][lastPatternIndex] ||
                                      ((currentPatternChar == '.' || s[i - 1] == currentPatternChar) && i >= 1 && match[i - 1][j]);
                    }
                }
                lastPatternIndex = j;
                ++j;
            }
            return match[s.size()][p.size()];
        }
    };

    时间复杂度

    @H_502_2@算法由2层扫描组成:外层扫描p的每一个子模式,内层扫描s的每一个字符。因此,该算法的时间复杂度为O(mn),其中m为p的子模式个数,n为s的字符个数。

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