leetcode 10. 正则表达式匹配(C++)

本是古典何须时尚 2023-07-16 13:56 75阅读 0赞

# 题目 #

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

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

说明:

s 可能为空，且只包含从 a-z 的小写字母。  
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 \*。  
示例 1:

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

示例 2:

输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入:
    s = "ab"
    p = ".*"
    输出: true
    解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
    s = "mississippi"
    p = "mis*is*p*."
    输出: false

来源：[10. 正则表达式匹配 - 力扣（LeetCode）][10. _ - _LeetCode]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

以下算法学习自官方题解：  
[正则表达式匹配 - 正则表达式匹配 - 力扣（LeetCode）][- _ - _LeetCode]

# 回溯法 #

*  如果没有星号（正则表达式中的 \* ），问题会很简单——我们只需要从左到右检查匹配串 s 是否能匹配模式串 p 的每一个字符。  
    当模式串中有星号时，我们需要检查匹配串 s 中的不同后缀，以判断它们是否能匹配模式串剩余的部分。一个直观的解法就是用回溯的方法来体现这种关系。  
    ***具体思路见代码中注释***

代码如下：

class Solution { 
    public:
        bool isMatch(string s, string p) { 
        	//若p为空，则需s同时为空才匹配
            if(p.empty())   return s.empty(); 
            //判断s的第1个字符是否直接匹配 
            bool first_match = !s.empty() && (p[0] == s[0] || p[0] == '.'); 
            //提前1个字符检测'*'，并分类讨论（'*'不可能出现在第1个位置）
            if(p.length() >= 2 && p[1] == '*') 
            	/* 可能匹配的两种情况： (1)isMatch(s, p.substr(2)) 代表'*'可能将前1字符重复了0次，故从'*'后位置继续匹配 (2)(first_match && isMatch(s.substr(1), p)) 代表s中第1个字符已匹配，留下p的第1个字符从s的下一个字符继续匹配 */     
                return isMatch(s, p.substr(2)) || (first_match && isMatch(s.substr(1), p));
            else
            	//暂无'*'且第1个字符匹配，继续匹配
                return first_match && isMatch(s.substr(1), p.substr(1));   
        }
    };

结果：

# 动态规划法 #

*  因为题目拥有 最优子结构 ，一个自然的想法是将中间结果保存起来。我们通过用  dp(i,j) \\text\{dp(i,j)\} dp(i,j)表示  text\[i:\] \\text\{text\[i:\]\} text\[i:\] 和  pattern\[j:\] \\text\{pattern\[j:\]\} pattern\[j:\]是否能匹配。我们可以用更短的字符串匹配问题来表示原本的问题。  
    我们用 \[方法 1\] 中同样的回溯方法，除此之外，因为函数  m a t c h ( t e x t \[ i : \] , p a t t e r n \[ j : \] ) match(text\[i:\], pattern\[j:\]) match(text\[i:\],pattern\[j:\])只会被调用一次，我们用  dp(i, j) \\text\{dp(i, j)\} dp(i, j)来应对剩余相同参数的函数调用，这帮助我们节省了字符串建立操作所需要的时间，也让我们可以将中间结果进行保存。

代码如下：

class Solution { 
    public:
        bool isMatch(string s, string p) { 
            bool dp[s.length()+1][p.length()+1] = { };
            dp[s.length()][p.length()] = 1;
            for (int i = s.length(); i >= 0; i--){ 
                for (int j = p.length() - 1; j >= 0; j--){ 
                    bool first_match = i < s.length() && (p[j] == s[i] || p[j] == '.');
                    if (j + 1 < p.length() && p[j+1] == '*'){ 
                        dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                    } 
                    else { 
                        dp[i][j] = first_match && dp[i+1][j+1];
                    }
                }
            }
            return dp[0][0];
        }
    };

结果：  
![在这里插入图片描述][20200319004754651.png]

[10. _ - _LeetCode]: https://leetcode-cn.com/problems/regular-expression-matching/
[- _ - _LeetCode]: https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode/
[20200319004754651.png]: /images/20230528/45ed16746d2a4411857e4aa079f606cf.png