LeetCode第10题思悟——正则表达式匹配（regular-expression-matching）

本文主要是介绍LeetCode第10题思悟——正则表达式匹配（regular-expression-matching），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

第十题——正则表达式匹配
- 题目要求
- 示例
- 我的思路
- 优秀解法
- 差别分析

第十题——正则表达式匹配

题目要求

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ，而不是部分字符串。

说明:

s可能为空，且只包含从 a-z`的小写字母。

p可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

示例

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

示例 5:

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

我的思路

这是我遇到的第一道困难级别的题，虽然费尽心思，得以通过，但是现在看来，代码真的是“又丑又烂”；甚至我都不太好意思写出来。可是“知耻近乎勇”，不反思，不总结，就提高不了水平；学如逆水行舟，不进则退。退，就不能和他人做兄弟了。

我认为难点在于“A*”这样的模式，所以如果在p中遇到“A*”，就会从当前位置开始，在s中寻找最多的“A”，然后产生一个“回溯点”。比如在s中，找到了连续5个A，即：“AAAAA”，到底是匹配5个呢还是只匹配一个呢？采用“贪心”的策略，会选择匹配5个，可是有可能匹配5个A后，后面就缺A了，特别是p为“A*A”时，应该匹配4个，然后留一个给后面的A。为了解决这个问题，就采用了回溯点（寻找结束后，分别记录发生回溯时，指向s和p的指针位置和可用次数）；

如果发生了不匹配（包含单个遍历字符串的指针出现越界的情况，因为如果匹配或者一定不匹配的话，应该是两个指针同时离开字符串），那么就检查是否有回溯点，有的话，就还原指针位置，然后将修改回溯点的可用次数并判断该回溯点时候还可以使用。

当s遍历完后，还需要考虑p中存在的null情况，即若干个连续的A*最后匹配了null。

以下为代码实现：

    public boolean isMatch(String s, String p) {if(s==null||s.equals("")){return checkNull(p.toCharArray(),0);}char[] testChars=s.toCharArray();char[] patternChars=p.toCharArray();int testLength= testChars.length;int patternLength=patternChars.length;LinkedList<RecallPoint> recallPoints=new LinkedList<>();RecallPoint recallPoint;boolean continueCheck=true;int testPointer=0;int patternPointer=0;char currentTestChar;char currentPatternChar;char nextPatternChar;int repeatTime;while(continueCheck){while(testPointer<testLength&&patternPointer<patternLength){currentPatternChar=patternChars[patternPointer];currentTestChar=testChars[testPointer];if(patternPointer+1<patternLength){//需要判断是否是A*nextPatternChar=patternChars[patternPointer+1];if(nextPatternChar=='*'){////从testPointer开始寻找testString里最长的重复字符串，需要记录长度repeatTime=0;while(isEqual(testChars[testPointer],currentPatternChar)){testPointer++;repeatTime++;if(testPointer>=testLength){break;}}if(repeatTime!=0){//不存在回溯点，相当于patternPointer中的A*匹配了null，recallPoints.push(new RecallPoint(testPointer - 1, patternPointer + 2, repeatTime-1));}patternPointer+=2;continue;}}if(isEqual(currentTestChar,currentPatternChar)){patternPointer++;testPointer++;}else{//在此检查是否还有回溯点，如果有的话，那么还可以继续recallPoint=recallPoints.peek();if(recallPoint==null){return false;//当前字符不匹配，而且都没有回溯点}else{testPointer=recallPoint.getTestPoint();patternPointer=recallPoint.getPatternPoint();recallPoint.reduceOnce();if(recallPoint.isInvalid()){//如果无效的话，那么弹出recallPoints.poll();}}}}//需要在此检查是否允许回溯if(testPointer>=testLength&&patternPointer>=patternLength){continueCheck=false;}else{if(testPointer==testLength){if(checkNull(patternChars,patternPointer)){return true;}}recallPoint=recallPoints.peek();if(recallPoint==null){return false;//发生指针越界，但是没有回溯点}else{testPointer=recallPoint.getTestPoint();patternPointer=recallPoint.getPatternPoint();recallPoint.reduceOnce();if(recallPoint.isInvalid()){//如果无效的话，那么弹出recallPoints.poll();}continueCheck=true;}}}return true;}public boolean isEqual(char test,char parten){if(parten=='.'){return true;}return test==parten;}public boolean checkNull(char[] pattern,int start){if((pattern.length-start)%2!=0){return false;}for(int i=start+1;i<pattern.length;i+=2){if(pattern[i]!='*'){return false;}}return true;}public class RecallPoint{private int testPoint;private int patternPoint;private int repeatTime;RecallPoint(int testPoint,int patternPoint,int repeatTime){this.testPoint=testPoint;this.patternPoint=patternPoint;this.repeatTime=repeatTime;}public boolean isInvalid(){return repeatTime<0;}public void reduceOnce(){repeatTime--;testPoint--;}public int getPatternPoint(){return patternPoint;}public int getTestPoint(){return testPoint;}}

最后，运行结果大概在40%左右吧（leetcode-cn），可以在代码中看到很多判断条件，而条件越多，出错率越高；虽然通过，但是并不满意。

优秀解法

使用递推思想，s=Sx；p=Pzy；记匹配符号为 “~” 。当y！=’*’ 时，则s~y 等价于S~Pz 并且 x~y；当y==’*'时，判断x和z是否匹配，如果x ~ z，那么只需要S ~ p即可认为s ~ p；如果x和z不匹配，那么只有s~ P是s~p（*匹配0次）；

可以看到，按照这样的解题思路，相当于利用f(n-1)推出f(n)。思路更加清晰。

代码如下：

public boolean isMatch(String s, String p) {if (p.length() == 0) {return s.length() == 0;}int m = s.length(), n = p.length();boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;for (int j = 1; j < n + 1; j++) {if (j >= 2 && p.charAt(j - 1) == '*' && dp[0][j - 2]) {dp[0][j] = true;}}for (int i = 1; i < m + 1; i++) {for (int j = 1; j < n + 1; j++) {if (p.charAt(j - 1) == '*') {dp[i][j] = j >= 2 && (dp[i][j - 2] || (i > 0 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') && dp[i - 1][j]));} else {dp[i][j] = (p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) && dp[i - 1][j - 1];}}}return dp[m][n];
}