题目

描述

• 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含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));
        }
    }
  }

• 时间复杂度：,JDK的substring的时间复杂度为，而匹配需要；
• 空间复杂度：,遍历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()];
    }
  }

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