题目描述

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'这种情况匹配失败

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

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

动态规划

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

根据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;
        }
    }
}

个人总结