题目描述

https://leetcode-cn.com/probl...

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

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

输入示例：

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

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

思路分析

双指针游走法（失败的方法）

自己最开始想到的方法，相当于是没有回溯的回溯法，导致s='aaa' p='a*a'这种情况匹配失败

暴力解法（官网答案叫做回溯法）

大体上就是通过递归的手段把匹配的问题抛给下一层

先从简单的想起，如果没有'.'和'*'，那么字符串的匹配就是很简单的两个指针i和j，分别对着s和p，然后依次对比。
这时，考虑加上'.'，对比字符s[i]和p[j]的时候，只需要把s[i]==p[j]加上p[j]=='.'的判断就可以
最后，再加上'*'的逻辑，根据对示例的观察，可以发现遇到*有这样几种情况（根据示例归纳出规律）：

1. 如aab和c*a*b，这里c*并没有匹配成功a，所以c*的含义就是取0个c
   
2. 再看aab和a*b，注意这里有两种情况
   1) aab的a算做匹配成功一个a，因此s的指针后移
   2) aab的a算做匹配成功0个a，这个是容易忽略掉的，这种时候p的指针后移两位
   
   因此，如图，当s和p的元素相等的时候，其实是有两条判断路径的，因此这里需要使用递归来同时结合两种路径的结果来判断

完整的aab匹配c*a*b的过程如下图：

写出伪代码

if p[j+1]=='*' and s[i]==p[j]:
    j+2 recursive || i+1 recursive
if p[j+1]=='*' and s[i]!=p[j]:
    j+2 recursive
if p[j+1] != '*':
    if s[i]==p[j]:
        i+1 and j+1 recursive
    else:
        return false

递归出口，

1. 没有*号了，两个单纯的字符比较失败，返回false
2. s和p都遍历完了，返回true
3. p没有*号了，s和p没有一起遍历完，返回false

动态规划

基于暴力解法，通过自顶向下的备忘录方式，或者自底向上的方式记录信息

根据pattern生成状态机

这种是标准的正则表达式的解决方式，通过解析请求的pattern，然后画出来一幅该正则式的有限状态机图，然后再对着图匹配字符串

代码实现

个人的错误解法

这个是个错误解法，aaa和a*a的情况会由于指针没有回溯导致匹配失败，稍后分析

class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0, j = 0;
        while(i < s.length() && j < p.length()) {
            if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
                if(j + 1 < p.length() && p.charAt(j+1) == '*') {
                    i++;
                } else {
                    i++;
                    j++;
                }
            } else if(j + 1 < p.length() && p.charAt(j+1) == '*') {
                j += 2;
            } else {
                return false;
            }
        }
        while(i == s.length() && j + 1 < p.length() && p.charAt(j+1) == '*') {
            j+=2;
        }
        if(i == s.length() && j == p.length()) {
            return true;
        } else {
            return false;
        }
    }
}

正确解法之回溯法

class Solution {
    public boolean isMatch(String s, String p) {
        return match(s, p, 0, s.length(), 0, p.length());
    }
    
    private boolean match(String s, String p, int sbegin, int send, int pbegin, int pend) {
        if(sbegin >= send && pbegin >= pend) {
            // exit
            return true;
        }
        if(pbegin + 1 < pend && p.charAt(pbegin + 1) == '*') {
            if(sbegin >= send) {
                // s is empty
                return match(s, p, sbegin, send, pbegin+2, pend);
            }
            if(s.charAt(sbegin) == p.charAt(pbegin) || p.charAt(pbegin) == '.') {
                return match(s, p, sbegin, send, pbegin+2, pend) || match(s, p, sbegin+1, send, pbegin, pend);
            } else {
                return match(s, p, sbegin, send, pbegin+2, pend);
            }
        } else {
            if(sbegin >= send || pbegin >= pend) {
                // exit
                return false;
            }
            if(s.charAt(sbegin) == p.charAt(pbegin) || p.charAt(pbegin) == '.') {
                return match(s, p, sbegin+1, send, pbegin+1, pend);
            } else {
                return false;
            }
        }
    }
}

个人总结

graph TD
A(分析例子) --> B(归纳出规律)
B --> C(画图)
C --> D(写伪代码确定递归推进和出口)

容易忘掉，例如aaa匹配a*a，匹配成功了a*也是可以当做匹配了0个的，此外注意指针直接推进是不行的，匹配完之后必须要判断后面的子串是否匹配成功（以此为依据才想到了递归）
不然容易出现a*直接把aaa都匹配完了，算作匹配失败