categories: leetcode

10.png

摘要里面放的是递归的方法，下面的是动态规划(Dynamic Programming)的方法。
10_2.png

题目描述

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
‘.’ Matches any single character.
‘‘ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
*Note:

  • s could be empty and contains only lowercase letters a-z.
  • p could be empty and contains only lowercase letters a-z, and characters like . or *.

Example 1: Input: s = “aa” p = “a” Output: false Explanation: “a” does not match the entire string “aa”.Example 2: Input: s = “aa” p = “a“ Output: true Explanation: ‘‘ means zero or more of the precedeng element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.Example 3: Input: s = “ab” p = “.“ Output: true Explanation: “.“ means “zero or more () of any character (.)”.Example 4: Input: s = “aab” p = “cab” Output: true Explanation: c can be repeated 0 times, a can be repeated 1 time.Therefore it matches “aab”.Example 5: Input: s = “mississippi” p = “misisp.” Output: false

参考代码

  1. //递归
  2. class Solution {
  3.     public boolean isMatch(String s, String p) {
  4.         if (p.isEmpty()) return s.isEmpty();
  5.         boolean first_match = (!s.isEmpty() &&
  6.                                (p.charAt(0) == s.charAt(0) || p.charAt(0) == '.'));
  8.         if (p.length() >= 2 && p.charAt(1) == '*'){
  9.           //(isMatch(s, p.substring(2))使第 p 中第三个字符进行匹配，
  10.           //(first_match && isMatch(s.substring(1), p))使 p 中 * 之前的字符进行匹配
  11.             return (isMatch(s, p.substring(2)) ||
  12.                     (first_match && isMatch(s.substring(1), p)));
  13.         } else {
  14.             return first_match && isMatch(s.substring(1), p.substring(1));
  15.         }
  16.     }
  17. }
  18. //DP
  21. class Solution {
  22.     public boolean isMatch(String s, String p) {
  23.        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
  24.         dp[s.length()][p.length()] = true;
  26.         for (int i = s.length(); i >= 0; i--){
  27.             for (int j = p.length() - 1; j >= 0; j--){
  28.                 boolean first_match = (i < s.length() && (p.charAt(j) == s.charAt(i) || p.charAt(j) == '.'));
  29.                 if (j + 1 < p.length() && p.charAt(j+1) == '*'){
  30.                     dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];//
  32.                 } else {
  33.                     dp[i][j] = first_match && dp[i+1][j+1];
  34.                 }
  35.             }
  36.         }
  37.         return dp[0][0];
  38.     }
  39. }

思路及总结

递归的思路： 大致是以 p 字段划分，两两进行递归。0,1,2个字符、纯字母和含有 . 的都较好理解。下面考虑含有 符号的。例如 aaacce 和 ace，(first_match && isMatch(s.substring(1), p)) 递归到 cce 和 ace 的情况，然后 (isMatch(s, p.substring(2)) 收拾最后一步，则 p 中 ac 的匹配结束，但是删除的字符是 a*，第三个字符可能在接下来的一组进行使用。
到了这一步，大致理解 If a star is present in the pattern, it will be in the second position \text{pattern[1]}pattern[1]. Then, we may ignore this part of the pattern, or delete a matching character in the text. If we have a match on the remaining strings after any of these operations, then the initial inputs matched. 是什么含义。但是看懂和写何止十万八千里，我还不知到要学习多少次，才能有这样的算法功底。复杂度有些复杂，大致应当是指空间复杂度为O(2^n)，空间复杂度是O(n^2)；
DP的思路：
了解一下DP：https://blog.csdn.net/zjkc050818/article/details/74532023
可能更适合看是视频：https://www.bilibili.com/video/av16544031/?spm_id_from=333.788.videocard.0
这里面提到了表格的DP：https://www.bilibili.com/video/av18512769?from=search&seid=1441380389563731271
这个 DP 的选与不选都不明显，而且很难判断出口，等做多了，想必能更好理解。
啥都不会是我最大的觉悟。。。。。别人是兔派，我是兔看派，第一次遇见dp，都说dp和博弈论是神仙题，我感受到了。

参考

https://leetcode.com/problems/regular-expression-matching/solution/