LeetCode正则表达式匹配（10题）dp和递归方法

&＃64;author:Jingdai
&＃64;date:2020.11.28

题目描述&＃xff08;10题&＃xff09;

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

• &＃39;.&＃39; 匹配任意单个字符
• &＃39;*&＃39; 匹配零个或多个前面的那一个元素

提示&＃xff1a;

• s 可能为空&＃xff0c;且只包含从 a-z 的小写字母
• p 可能为空&＃xff0c;且只包含从 a-z 的小写字母&＃xff0c;以及字符 . 和 *
• 保证每次出现字符 * 时&＃xff0c;前面都匹配到有效的字符

示例1

输入: s &＃61; "aa" p &＃61; "a*"
输出: true


示例2

输入: s &＃61; "ab" p &＃61; ".*"
输出: true


思路及代码

这个题目可以用动态规划或递归来解决&＃xff0c;思路都差不多&＃xff0c;这里先介绍 dp 的方法&＃xff0c;然后介绍递归的方法。

• dp 方法
  首先要明确匹配的含义&＃xff0c;这点很重要&＃xff0c;这也是很多人第一次做的时候懵逼的原因&＃xff08;我就是&＃xff09;。匹配的含义是正则表达式 p 和字符串 s 以任何一种方式匹配就算匹配。比如字符串 "aa" 和 正则表达式 "a*a*" &＃xff0c;这里有好几种匹配方式&＃xff0c;比如第一个 * 表示2个a&＃xff0c;第二个 * 表示0 个 a&＃xff1b;或者第一个 * 表示1个a&＃xff0c;第二个 * 表示1个a。但要注意&＃xff0c;只要有任何一种方式使正则表达式 p 和字符串 s 匹配了&＃xff0c;那么就算是匹配了&＃xff0c;而不用所有的方式都匹配。

  接下来看 dp&＃xff0c;如何定义状态呢&＃xff1f;我们这里定义 dp[i][j] 表示字符串 s 的前 i 个字母和正则表达式 p 的前 j 个字母是否匹配&＃xff08;注意&＃xff1a;i&＃xff0c;j 不是下标&＃xff0c;后同&＃xff09;。

  先看初始状态&＃xff0c;首先很容易得到 dp[0][0] 为 true&＃xff08;s 的前0个字母和 p 的前 0 个字母&＃xff09;&＃xff1b;然后当 j 等于 0 时&＃xff08;p的前0个字母&＃xff09;&＃xff0c;只有当 i 等于0时 dp[i][j] 为true&＃xff0c;否则都为false。但是当 i 等于 0 时&＃xff0c;dp[i][j] 需要讨论。如图&＃xff0c;当 p 为 "a*b*c" 时&＃xff0c; dp[0][1] 显然为 false &＃xff0c;但是 dp[0][2] 为true&＃xff08;j &＃61; 2 的 * 代表前面有0个a&＃xff09;&＃xff1b; dp[0][3] 为 false&＃xff0c; dp[0][4] 又是 true &＃xff08;j &＃61; 4 的 * 代表前面有0个a&＃xff09;。可以得出当 i 等于0时有&＃xff1a; dp[i][j] &＃61; p.charAt(j-1) &＃61;&＃61; &＃39;*&＃39; && dp[i][j-2] 。
  
  下面就是 dp 的重点了&＃xff0c;也是这个题的难点&＃xff0c;状态转移方程。

  从最简单的开始&＃xff0c;如图&＃xff0c;当 s 的第 i 个元素&＃xff08;不是下标&＃xff0c;后同&＃xff09;和 p 的第 j 个元素&＃xff08;不是下标&＃xff0c;后同&＃xff09;相同时&＃xff08;或 p 的第 j 个元素是 &＃39;.&＃39; &＃xff09;&＃xff0c;那么很容易得出 dp[i][j] &＃61; dp[i-1][j-1] 。
  
  当 s 的第 i 个元素和 p 的第 j 个元素不同且 p 的第 j 个元素为 &＃39;*&＃39; 时&＃xff0c;又分为两种情况。

  1. 如图&＃xff0c;当 s 的第 i 个元素和 p 的第 j-1 个元素不同时&＃xff0c;那么只有将 p 的第 j-1 个元素和第 j 个元素去掉才有可能使它们相同&＃xff0c;故此时 * 只能代表 0 个前面的元素&＃xff0c;此时 dp[i][j] &＃61; dp[i][j-2] 。

     

  2. 当 s 的第 i 个元素和 p 的第 j-1 个元素相同时&＃xff0c;如图&＃xff0c;可以发现不管 i 前有几个相同的元素&＃xff0c;如 "cba"、"cbaa"、"cbaaa"&＃xff0c;dp[i][j] 的结果总和 dp[i-1][j] 的结果相同&＃xff0c;相当于这里的 i 和 j 都往前移动一位&＃xff0c;j 移动代表 a* 少匹配一个 a &＃xff0c;不用动&＃xff0c;故得到 dp[i][j] &＃61; dp[i-1][j] 。

     

     但是还有特殊的情况&＃xff0c;如图&＃xff0c;例如当 s 为 "a" , p 为 "aa*" 时&＃xff0c;这时只能删除 a*&＃xff0c;才能使 s 和 p 匹配。此时 dp[i][j] &＃61; dp[i][j-2] 。前面说过&＃xff0c;只要有一种方式匹配成功就算匹配&＃xff0c;所以最后的递推式为 dp[i][j] &＃61; dp[i-1][j] || dp[i][j-2] 。

     

综上&＃xff0c;所有情况的递推式为&＃xff1a;

1. 当 s 的第 i 个元素和 p 的第 j 个元素相同时&＃xff1a;dp[i][j] &＃61; dp[i-1][j-1]
2. 当 s 的第 i 个元素和 p 的第 j 个元素不同且 p 的第 j 个元素为 &＃39;*&＃39; 时&＃xff1a;
   1. 当 s 的第 i 个元素和 p 的第 j-1 个元素不同时&＃xff1a;dp[i][j] &＃61; dp[i][j-2]
   2. 当 s 的第 i 个元素和 p 的第 j-1 个元素相同时&＃xff1a;dp[i][j] &＃61; dp[i-1][j] || dp[i][j-2]
3. 其他情况&＃xff1a;dp[i][j] &＃61; false

代码如下。

public boolean isMatch(String s, String p) {if (s &＃61;&＃61; null || p &＃61;&＃61; null)return false;int lenS &＃61; s.length();int lenP &＃61; p.length();char[] sChars &＃61; s.toCharArray();char[] pChars &＃61; p.toCharArray();boolean[][] dp &＃61; new boolean[lenS&＃43;1][lenP&＃43;1];for (int i &＃61; 0; i <&＃61; lenS; i&＃43;&＃43;) {for (int j &＃61; 0; j <&＃61; lenP; j&＃43;&＃43;) {if (j &＃61;&＃61; 0) {if (i &＃61;&＃61; 0) {dp[i][j] &＃61; true;} // or is falsecontinue;}if (i &＃61;&＃61; 0) { // j !&＃61; 0if (j - 3 >&＃61; 0) {dp[i][j] &＃61; pChars[j-1] &＃61;&＃61; &＃39;*&＃39; && dp[i][j-2];} else {dp[i][j] &＃61; pChars[j-1] &＃61;&＃61; &＃39;*&＃39;; // the first cant be *}continue;}if (sChars[i-1] &＃61;&＃61; pChars[j-1] || pChars[j-1] &＃61;&＃61; &＃39;.&＃39;) {dp[i][j] &＃61; dp[i-1][j-1];} else if (pChars[j-1] &＃61;&＃61; &＃39;*&＃39;) {if (pChars[j-2] &＃61;&＃61; sChars[i-1] || pChars[j-2] &＃61;&＃61; &＃39;.&＃39;) {dp[i][j] &＃61; dp[i-1][j] || dp[i][j-2];} else {dp[i][j] &＃61; dp[i][j-2];}}}}return dp[lenS][lenP];
}


• 递归方法
  和 dp 相同&＃xff0c;递推的式子完全一样&＃xff0c;只要注意递归出口就好。递归出口就是 dp 方法中的初始化部分&＃xff0c;如果上面的 dp 方法懂了&＃xff0c;递归方法就非常容易看懂&＃xff0c;直接上代码。

public boolean isMatch(String s, String p) {if (s &＃61;&＃61; null || p &＃61;&＃61; null) {return false;}return isMatch(s, p, s.length(), p.length());
}public boolean isMatch(String s, String p, int firstSLetters, int firstPLetters) {if (firstPLetters &＃61;&＃61; 0) {if (firstSLetters &＃61;&＃61; 0) {return true;} else {return false;}}if (firstSLetters &＃61;&＃61; 0) {if (p.charAt(firstPLetters-1) &＃61;&＃61; &＃39;*&＃39;) {return isMatch(s, p, firstSLetters, firstPLetters-2);} else {return false;}}if (s.charAt(firstSLetters-1) &＃61;&＃61; p.charAt(firstPLetters-1) || p.charAt(firstPLetters-1) &＃61;&＃61; &＃39;.&＃39;) {return isMatch(s, p, firstSLetters-1, firstPLetters-1);} else if (p.charAt(firstPLetters-1) &＃61;&＃61; &＃39;*&＃39;) {if (s.charAt(firstSLetters-1) &＃61;&＃61; p.charAt(firstPLetters-2) || p.charAt(firstPLetters-2) &＃61;&＃61; &＃39;.&＃39;) {return isMatch(s, p, firstSLetters-1, firstPLetters) || isMatch(s, p, firstSLetters, firstPLetters-2);} else {return isMatch(s, p, firstSLetters, firstPLetters-2);}} return false;
}