题目描述
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; } }}