题目描述

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

个人总结