题目

描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配

方法一

思路

pattern中总共分为三种字符，普通字符，'.'，'*'，其中普通字符与'.'很好处理，只要与str中相应位置的字符比较即可，对于普通字符只要判断是否相同，而字符'.'则只要str对应位置不为空即可；
对于字符'*'，需要考虑忽略前面一个字符或者是拓展前面一个字符，便存在如下递推公式：
前提是前面的字符串已经匹配成功， $图片说明$ ,分别表示'*'匹配多个字符以及不匹配字符。

具体步骤

代码如下：

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param str string字符串 
   * @param pattern string字符串 
   * @return bool布尔型
   */
  public boolean match (String str, String pattern) {
     if (pattern.length() == 0) {
          return str.length() == 0;
      }
      // 第一个字符必然不会是'*',所以可以直接比较
      boolean match = (str.length() > 0 && 
                      (str.charAt(0) == pattern.charAt(0) ||
                       pattern.charAt(0) == '.'));
      // 有*
      if (pattern.length() > 1 && pattern.charAt(1) == '*') {
          // 0个 || 多个
          return match(str, pattern.substring(2)) || (match && match(str.substring(1), pattern));
      }
      // 无*
      else {
          return match && match(str.substring(1), pattern.substring(1));
      }
  }
}

时间复杂度： $O(m^2n^{2})$ ,JDK的substring的时间复杂度为 $O(n)$ ，而匹配需要 $O(mn)$ ；
空间复杂度： $O(mn)$ ,遍历str以及pattern。

方法二

思路

采用动态规划的方法解题，创建二维数组dp，dp[i][j]表示从0~i-1的str与从0~j-1的pattern是否匹配，匹配为true，反之则为false；
pattern中总共分为三种字符，普通字符，'.'，'*'，其中普通字符与'.'很好处理，只要与str中相应位置的字符比较即可，对于普通字符只要判断是否相同，而字符'.'则只要str对应位置不为空即可；
最为复杂的就是字符'*'，该字符可以匹配0或多个前面的字符，所以需要考虑以下两种情况：
a.当前位pattern[j-1] == '*'，那么需要判断以下三种情况：
1. dp[i][j - 2]，即 j-2 位的pattern能满足，则 i-1 位是 '*' 作为任意数量的值必定能满足匹配
2. dp[i - 1][j] && str[i - 1] == pattern[j - 2]；即让字符 pattern[j-2]多出现几次，看能否匹配
3. dp[i - 1][j] && pattern[j - 2] == '.', 即让字符 '.' 多出现 1 次时，能否匹配；
b.当前位pattern[j-1] != '*'，那么只需要判断当前位是否满足条件即能否匹配到str对应位i，可以dp[i+1][j+1] = true。
初始化，考虑字符串为空，但是pattern不为空的情况：dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*', 即当前pattern的0到j位是true还是false，取决于dp[0][j-2]是否匹配，以及 pattern的当前位的上一位是否为'*'。
Tip:这里有个有点绕的下标表示，对于dp来说下标0表示空串，而对于str以及pattern来说，下标0表示第一个字符。

具体步骤

参考下图示例

代码如下

import java.util.*;
public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   *
   * 
   * @param str string字符串 
   * @param pattern string字符串 
   * @return bool布尔型
   */
  public boolean match (String str, String pattern) {
      // 加上空串，0~n
      boolean[][] dp = new boolean[str.length()+1][pattern.length()+1];
      // 两个都是空串
      dp[0][0] = true;
      // 字符串为空，正则表达式不为空
      for (int i = 2; i < dp[0].length; ++i){
          // 正则表达式从下标0开始
          if (pattern.charAt(i-1) == '*'){
              // 从下标1开始
              dp[0][i] = dp[0][i-2];
          }
      }
      // 状态转移
      for (int i = 1;i < dp.length;++i){
          for (int j = 1;j < dp[0].length;++j){
              if (pattern.charAt(j-1) != '*'){
                  if (pattern.charAt(j-1) == '.' || 
                      pattern.charAt(j-1) == str.charAt(i-1)){
                      dp[i][j] = dp[i-1][j-1];
                  }
              }else if (j >= 2 && pattern.charAt(j - 1) == '*'){
                  // 对于包含 * 的匹配
                  // 当前一位为 '.', 或者字符相等,则匹配
                  if (pattern.charAt(j - 2) == '.' ||
                      pattern.charAt(j - 2) == str.charAt(i - 1)) {
                      dp[i][j] = dp[i][j - 2] ||
                          dp[i - 1][j - 2] ||
                          dp[i - 1][j];
                  } else {
                      // 否则只能不匹配
                      dp[i][j] = dp[i][j - 2];
                  }
              }
          }
      }
      return dp[str.length()][pattern.length()];
  }
}

时间复杂度： $O(mn)$ ,m = str.length(),n = pattern.length(),遍历整个dp数组；
空间复杂度： $O(mn)$ ,二维数组dp。

题解 | #正则表达式匹配#

题目

描述

方法一

思路

具体步骤

方法二

思路

具体步骤