Skip to content

Latest commit

 

History

History
112 lines (85 loc) · 4.76 KB

10. Regular Expression Matching.md

File metadata and controls

112 lines (85 loc) · 4.76 KB

思路

仅包含'.'和'*'以及小写字母的正则表达式匹配。模式中的字符

  • '.'表示任意一个字符;
  • 而'*'表示它前面的字符可以出现任意次(包含0次)。

思路一、递归

递归解法,先考虑如何匹配s中的第一个字符,再递归匹配剩余部分。

由于模式的第二个字符可能是'*',所以模式的第一个字符不一定要匹配,例如模式'a*bc'可以匹配'bc',所以我们按照模式中 第二个字符是否为'*' 对情况分类:

  • 若是,即p[1] == '*',因为可以匹配第一个字符p[0]0次或>0次,所以有两条路可尝试:

    • (1) 尝试匹配0次,此时递归考虑模式p的剩余部分是否与s匹配即可,即若isMatch(s, p.substr(2))==true,则返回true,程序结束,否则进入(2)。
    • (2) 尝试匹配>0次,此时前提是p和s的第一个字符匹配成功,即(s[0] == p[0] || '.' == p[0]),然后递归考虑模式p是否与s的剩余部分是否匹配即可,即若isMatch(s.substr(1), p)==true,则返回true,程序结束。若(1)(2)都不成立,则匹配失败,返回false,程序结束。
  • 若不是,那就比较简单了,直接判断模式p和s的第一个字符是否匹配然后再递归匹配剩余即可,即返回(s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p.substr(1))

另外还有一个重要的点就是递归出口,先来看三个边界情况:

s p 匹配结果
true
不空 false
不空 无法判断, 例若s为空, 则p='x*'时匹配成功, p='x'时匹配失败

由上表可知递归出口为

if(p.empty()) return s.empty();

所以s为空但p不为空时不会立即返回,所以在访问s[0]之前需要先判断s是否为空,见代码。

这种方法由于递归调用次数比较多,所以亲测比较慢。下面思路二采用动态规划迭代的方式要快很多。

思路二、动归

也可以使用动态规划的方法,因为匹配问题可以分解为单个字符进行匹配的子问题。

我们定义状态:

如果 s[0, 1, ..., i-1] 与 p[0, 1, ..., j-1] 匹配则 dp[i][j] = true 否则 dp[i][j] = false. 

所以初始状态为dp[0][0] = true表示两个空串相匹配,其他全部初始为false。

根据思路一的分析,我们有类似的状态转移方程:

  • 如果模式最后一个字符(即p[j-1])为'*',则有两条路:
    • (1)尝试匹配0次,即p[j-2]p[j-1]都没用,所以如果dp[i][j-2] == truedp[i][j]为true;
    • (2)尝试匹配1次,即在前一个模式字符p[j-2]与待匹配字符s[i-1]相匹配的情况下,如果dp[i-1][j]=truedp[i][j]为true;
  • 否则,即模式最后一个字符不为'*',则只能检查这个字符是否与待匹配字符是否匹配了,若匹配,且dp[i-1][j-1]=truedp[i][j]为true。

与思路一类似,由于s为空但p不为空时可能成功匹配,所以第一层循环i应该从0开始而不是从1开始,见代码。

C++

思路一

class Solution {
public:
    bool isMatch(string s, string p) {
        if(p.empty()) return s.empty();
        
        #define MATCH (s[0] == p[0] || '.' == p[0])
        
        // p的第二个字符是*
        if(p[1] == '*'){ // 不会溢出, 因为p[p.size()] == '\0'
            // 匹配0个字符, 此时若s为空也可能匹配成功
            if(isMatch(s, p.substr(2))) return true; 
            // 匹配1个字符
            if(s.size() && MATCH && isMatch(s.substr(1), p)) return true; 
            return false;
        }
        
        // p的第二个字符不是*
        return s.size() && MATCH && isMatch(s.substr(1), p.substr(1));
    }
};

思路二

class Solution {
public:
    bool isMatch(string s, string p) {
        // if(p.empty()) return s.empty();
        int sn = s.size(), pn = p.size();
        vector<vector<bool>>dp(sn + 1, vector<bool>(pn + 1, false));
        dp[0][0] = true;
        
        for(int i = 0; i <= sn; i++){ // i = 0代表s为空的情况, 所以不能从1开始
            for(int j = 1; j <= pn; j++){
                if(j > 1 && p[j - 1] == '*'){ // 最后一个字符为*
                    // 匹配0个字符
                    if(dp[i][j-2]) dp[i][j] = true;
                    // 匹配1个字符
                    else if(i > 0 && (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && dp[i-1][j]) 
                        dp[i][j] = true;
                }
                // 最后一个字符不是*
                else if(i > 0 && (s[i - 1] == p[j - 1] || '.' == p[j - 1]) && dp[i-1][j-1]) 
                    dp[i][j] = true;
            }
        }
        
        return dp[sn][pn];
    }
};