正则表达式

正则表达式匹配

题目描述：

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

解题思路：

（1）这个题目是典型的二维动态规划题目；
eg:
s = "aaab"
p = "cab"
1.1 首先建立dp数组dp[s.size() + 1][p.size() + 1]
需要从空字符串进行思考，所以需要+1
其中dp[i][j]对应的字符比较应该是s[i-1]和p[j-1]

（2）问题主要集中在如何处理号，号的作用是两个
2.1 去除前面一个无关的字符，dp[i][j]的结果就变成了dp[i][j-2]; 比较 s[0:i]和p[0:j-3]的匹配结果
2.2 重复前面一个字符n次（n可以为0）dp[i][j]的结果需要看 s[i-1]和p[j-2]的匹配结果 和 dp[i-1][j]的结果

代码：

class Solution {
public:
    bool isMatch(string s, string p) {
    int s_len = s.size(), p_len = p.size();
    // dp[i][j]是由s[i-1]和p[j-1]决定的
    // 其中i=0 和 j=0都是表示空字符串的时候
    bool **dp = new bool*[s_len + 1];
    for(int i = 0; i <= s_len; ++i){
        dp[i] = new bool[p_len + 1];
    }
    // p为空，但s不为空时候肯定是false
    for(int i = 0; i <= s_len; ++i)
        dp[i][0] = false;
    
    // 两者都为空的时候为true
    dp[0][0] = true;
    
    for(int i = 0; i <= s_len; ++i)
        for(int j = 1; j <= p_len; ++j){ // j=0的情况已经初始化了
            if(p[j-1] == '*'){
                /*
                 p[j-1]=='*'的时候有两种情况：
                 （1）当*号的作用是去除p[j-2]，因此需要看s[0:i-1]和p[0:j-3]的匹配效果==>dp[i][j-2]；
                    同时还考虑到了i=0的情况，*对于dp[0][j]的填充；同时就算p[j-1] == s[i -1]，同样也可能需要去除p[j-2]，eg: a 与 aa*
                 （2）p[j-1] == s[i -1]或者p[j-1] == '.'的时候，*号的作用是重复p[j-1]这个字符n（n可以为0）次，s[0:i-1]和p[0:j-1]如果能匹配的上，
                 证明s[0:i-2]和p[0:j-1]肯定也是匹配上的==>dp[i-1][j]; eg: aab 与 ab*匹配不上
                 */
                dp[i][j] = (dp[i][j-2]) || (i > 0 && (p[j-2] == s[i -1] || p[j-2] == '.') && dp[i-1][j]);
            }else{
                // 正常比较情况
                dp[i][j] =  i > 0 && dp[i-1][j-1] && (p[j-1] == '.' || p[j-1] == s[i-1]);
            }
        }
    
    return dp[s_len][p_len];
    }
};
 
// 递归的方式
/*
bool isMatch(string s, string p) {
        if(0 == p.size()) return (0 == s.size());
        bool is_match = s.size() > 0 && (s[0] == p[0] || p[0] == '.');
        if(p.size() > 0 && p[1] == '*'){
            return isMatch(s, p.substr(2)) || (is_match && isMatch(s.substr(1), p));
        }else{
            return is_match && isMatch(s.substr(1), p.substr(1));
        }
 }
*/

自己编写的版本：

class Solution {
public:
    bool isMatch(string s, string p) {
        bool **dp;
        int len_s = s.size(), len_p = p.size();
        dp = new bool*[len_s + 1];
        for(int i = 0; i < len_s + 1; ++i) {
            dp[i] = new bool[len_p + 1];
        }
        dp[0][0] = true;
        for(int i = 1; i < len_s + 1; ++i) {
            dp[i][0] = false;
        }
        for(int i = 0; i < len_s + 1; ++i) {
            for(int j = 1; j < len_p + 1; ++j) {
                // *比较特殊需要单独判断 
                if(p[j - 1] == '*') {
                    // 当前dp[i][j]的前一个位置 s[i - 1] 和 p[j - 1]是可以匹配的
                    // 如果前面字符串就是可以匹配的了，那么*号的作用就是重复0次
                    // 如果前面的字符串不能完成匹配
                    if(i > 0 && j > 1 && (p[j - 2] == s[i - 1] || p[j -2] == '.')) {
                        // 重复前面的n次  --> dp[i-1][j]  ; 去除多余的相同字符 --->dp[i][j-2]
                        dp[i][j] = dp[i - 1][j] || dp[i][j -2];
                    } else if(j > 1){  // 前面字符不相等的时候用*进行删除来获取是否能够匹配
                        dp[i][j] = dp[i][j -2];
                    } else { // *放在最开始的时候是不允许的（前面必须有字符），不能匹配
                        dp[i][j] = false;
                    }
                } else {
                    if(i > 0 && (s[i-1] == p[j-1] || p[j-1] == '.'))
                        dp[i][j] = dp[i - 1][j - 1];
                    else
                        dp[i][j] = false;
                }
            }
        }
        // for(int i = 0; i < len_s + 1; ++i) {
        //     for(int j = 0; j < len_p + 1; ++j) {
        //         if(dp[i][j] == true)
        //             cout<<"1"<<"  ";
        //         else
        //             cout<<"0"<<"  ";
        //     }
        //     cout<<endl;
        // }
        return dp[len_s][len_p];
    }
};