Leetcode 10. 正则表达式匹配

🕗 发布于 2024-10-08 15:41 leetcode 正则表达式算法

1.题目基本信息

1.1.题目描述

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

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

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

1.2.题目地址

https://leetcode.cn/problems/regular-expression-matching/description/

2.解题方法

2.1.解题思路

动态规划

2.2.解题步骤

在这里插入图片描述

第一步，状态定义；dp[i][j]为s的前i个字符串和p的前j个字符串是否匹配

第二步，状态初始化。初始化当匹配字符串为空时的匹配状态（即j=0时的状态），因为除了原字符串为空时，dp[0][0]=True，其余的情况下dp[x][0]=False，所以只需要初始化dp[0][0]=True即可

第三步，状态转移。当判断前i个字符和前j个匹配字符是否匹配时，这里先预先定义俩字符匹配为匹配字符为.或者匹配字符和原字符两者相等。

如果最后一个匹配字符为号，并且倒数第二个匹配字符和原字符串最后一个字符匹配，可以选择让匹配一次，去除当前s子串中匹配的部分，此时的状态转移为dp[i][j]=dp[i-1][j]，当选择让*匹配0个，则去除匹配子串中的x*组合，此时状态转移为dp[i][j]=dp[i][j-2]；
如果最后一个匹配字符为*，并且倒数第二个匹配字符和原字符串最后一个字符不匹配，则只能选择让*匹配0次，此时dp[i][j]=dp[i][j-2]；
如果最后一个匹配字符不为*号，并且该匹配字符与原字符串中最后一个字符匹配，此时的转移方程为dp[i][j]=dp[i-1][j-1]；
如果最后一个匹配字符不为*号，并且该匹配字符与原字符串最后一个字符不匹配，则当前的原字符串和匹配字符串一定无法匹配，即dp[i][j]=False。

经过遍历，最终的dp[sLen][pLen]即为题解

3.解题代码

Python代码

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        sLen,pLen=len(s),len(p)
        # 第一步，状态定义；dp[i][j]为s的前i个字符串和p的前j个字符串是否匹配
        dp=[[False]*(pLen+1) for i in range(sLen+1)]
        # 第二步，状态初始化。初始化当匹配字符串为空时的匹配状态（即j=0时的状态），因为除了原字符串为空时，dp[0][0]=True，其余的情况下dp[x][0]=False，所以只需要初始化dp[0][0]=True即可
        dp[0][0]=True   # 两个都是空字符串时，匹配
        # 第三步，状态转移。当判断前i个字符和前j个匹配字符是否匹配时，这里先预先定义俩字符匹配为匹配字符为.或者匹配字符和原字符两者相等。如果最后一个匹配字符为*号，并且倒数第二个匹配字符和原字符串最后一个字符匹配，可以选择让*匹配一次，去除当前s子串中匹配的部分，此时的状态转移为dp[i][j]=dp[i-1][j]，当选择让*匹配0个，则去除匹配子串中的x*组合，此时状态转移为dp[i][j]=dp[i][j-2]；如果最后一个匹配字符为*，并且倒数第二个匹配字符和原字符串最后一个字符不匹配，则只能选择让*匹配0次，此时dp[i][j]=dp[i][j-2]；如果最后一个匹配字符不为*号，并且该匹配字符与原字符串中最后一个字符匹配，此时的转移方程为dp[i][j]=dp[i-1][j-1]；如果最后一个匹配字符不为*号，并且该匹配字符与原字符串最后一个字符不匹配，则当前的原字符串和匹配字符串一定无法匹配，即dp[i][j]=False。经过遍历，最终的dp[sLen][pLen]即为题解
        # > 判断s[i]字符和p的p[j]字符是否匹配
        def match(i,j):
            if i<0 or j<0:
                return False
            if p[j]==".":
                return True
            elif p[j]==s[i]:
                return True
            else:
                return False
        for i in range(sLen+1):
            for j in range(1,pLen+1):
                if p[j-1]!="*":
                    if match(i-1,j-1):
                        dp[i][j]=dp[i-1][j-1]
                    else:
                        dp[i][j]=False
                else:
                    if match(i-1,j-2):
                        dp[i][j]=dp[i-1][j] or dp[i][j-2]
                    else:
                        dp[i][j]=dp[i][j-2]
        # print(dp[sLen][pLen])
        return dp[sLen][pLen]

C++代码

class Solution {
public:
    bool match(int i,int j,string s,string p){
        if(i<0 || j<0){
            return false;
        }
        if(p[j]=='.'){
            return true;
        }else if(p[j]==s[i]){
            return true;
        }else{
            return false;
        }
    }
    bool isMatch(string s, string p) {
        int sLen=s.size(),pLen=p.size();
        vector<vector<bool>> dp(sLen+1,vector<bool>(pLen+1,false));
        dp[0][0]=true;
        for(int i=0;i<sLen+1;++i){
            for(int j=1;j<pLen+1;++j){
                if(p[j-1]!='*'){
                    if(match(i-1,j-1,s,p)){
                        dp[i][j]=dp[i-1][j-1];
                    }else{
                        dp[i][j]=false;
                    }
                }else{
                    if(match(i-1,j-2,s,p)){
                        dp[i][j]=dp[i-1][j] || dp[i][j-2];
                    }else{
                        dp[i][j]=dp[i][j-2];
                    }
                }
            }
        }
        return dp[sLen][pLen];
    }
};

4.执行结果