LeetCode-10 正则表达式匹配

- 日理万妓 2022-12-13 04:48 167阅读 0赞

[LeetCode10][]

看似是一个字符串问题，实则是动态规划问题

越长的字符串匹配结果依赖于较短的字符串匹配结果

首先有两层for循环，外层是遍历源字符串s，内层是遍历正则串p，这样可以将字符串由短至长对正则表达式进行匹配

设 d p \[ i \] \[ j \] dp\[i\]\[j\] dp\[i\]\[j\]表示s串到 i i i位置和p串到 j j j位置的匹配结果，有0和1两种

对于p正则串，有两个特殊符号 . . .和 ∗ \* ∗

*  如果遇到了 ∗ \* ∗
    
     ∗ \* ∗前面的字符可以为0个或者多个，判断这个 x ∗ x\* x∗组合的 p \[ j − 1 \] p\[j-1\] p\[j−1\]是不是等于字符串s的当前符号 s \[ i \] s\[i\] s\[i\]
    
    1.  如果false，说明字符为0个， d p \[ i \] \[ j \] = d p \[ i \] \[ j − 2 \] dp\[i\]\[j\] = dp\[i\]\[j-2\] dp\[i\]\[j\]=dp\[i\]\[j−2\]，就当没看见这个 x ∗ x\* x∗组合
    2.  如果true，说明字符至少有一个， d p \[ i \] \[ j \] = d \[ i \] \[ j − 2 \] 或 d p \[ i − 1 \] \[ j \] dp\[i\]\[j\] = d\[i\]\[j-2\] 或 dp\[i-1\]\[j\] dp\[i\]\[j\]=d\[i\]\[j−2\]或dp\[i−1\]\[j\]
 *  如果没遇到 ∗ \* ∗
    
    1.  直接判断 s \[ i \] s\[i\] s\[i\]这个字符是不是和正则串 p \[ j \] p\[j\] p\[j\]相同
    2.  如果 p \[ j \] p\[j\] p\[j\]是正则 . . .号，就肯定相同

class Solution {
        
    public:
        bool isMatch(string s, string p) {
        
            int dp[1001][1001];
            memset(dp, 0, sizeof(dp));
            dp[0][0] = 1;
    
            // 判断是否相同
            auto isMatch = [&](int i, int j){
        
                if(i<=0)return false;
                if(p[j-1] == '.')return true;
                return s[i-1]==p[j-1];
            };
    
            for(int i=0; i<=s.length(); i++) {
        
                for(int j=1; j<=p.length(); j++) {
        
    
                    if(p[j-1] == '*' && j>=2){
          // 是*
    
                        dp[i][j] |= dp[i][j-2]; // 0个前面符号的情况
    
                        if(isMatch(i, j-1))   
                            dp[i][j] |= dp[i-1][j]; // 如果多个成立了就往下匹配
    
                    }else{
        
                        if(isMatch(i, j)) 
                            dp[i][j] |= dp[i-1][j-1];
                    }
    
                }
            }
            return dp[s.length()][p.length()]==1;
        }
    };

[LeetCode10]: https://leetcode-cn.com/problems/regular-expression-matching