题目描述

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

示例1

输入：
"aaa","a*a"

返回值：
true

从题已知信息

1）. 代表1次匹配任意字符
2）* 代表0次或任意次匹配 * 前面的字符

方法一: 动态规划

思路和算法

动态规划难就难在怎么找出状态转移方程

假设主串为 A ，模式串为B
如果我们找模式串的最后一次字符来找转移方程，根据题意只有下面3种情况

  1. 没有 . 和 * 那就是直接匹配 A[i-1] = B[j-1] ，继续向前匹配 A[i-2] = B[j-2]
  2. 如果是 . 那就是直接相等了 A[i-1] = B[j-1]，继续向前匹配 A[i-2] = B[j-2]
  3. 如果是 * 就复杂点了，代表了 c* = B[j-2]
    1. 场景a：A[n-1] 没有 c , 那 B 最后2个字符忽略 ，继续向前匹配 A[i-1] = B[j-3]
    2. 场景b：A[n-1] 中有 c , A中的 c 可以有一个或者多个，继续向前匹配 A[i-2] = B[j-2]

      c代表 * 前面的匹配字符

转移方程:

假设dp[i][j] 代表 A 的前 i 个和 B 的前 j 个能否匹配

  1. 对于第1种，第2种情况： dp[i][j] = dp[i-1]dp[j-1]，他们是根据前面的情况来判断是否能匹配 + 自己这次判断能否能匹配
  2. 第于第3种情况，又有2种以下场景：
    1. 场景a：直接忽略：dp[i][j] = dp[i][j-2]
    2. 场景b：进行匹配: dp[i][j] = dp[i-1][j] , 主串前移，模式串不动
  3. 返回值就是: dp[A.length][B.length]

base case:

  1. 空串为true , dp[0][0] = true
  2. 空串 A 跟 空串正则必不匹配
    1. dp[i][0] = false

全部代码如下：

自底向上实现（部分代码可以写成一行，为了方便解释，分行了）：

import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
       // str = A , pattern = B
        int n = str.length();
        int m = pattern.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        //base case
        //空串为true , dp[0][0] = true
        dp[0][0] = true;
        //空串 A 跟 空串正则必不匹配, dp[i][0] = false
        for (int i = 1; i < n; i++) {
            dp[i][0] = false;
        }
        //转移方程，根据前面分析的来写
        for (int i = 0; i <= n; i++) {
            //上面已经处理过 j == 0 的情况了，下标直接从1开始
            for (int j = 1; j <= m; j++) {
                //分成空正则和非空正则两种
                //非空正则分为两种情况 * 和 非*
                if (pattern.charAt(j - 1) != '*') {
                    // 只要情况1或者情况2成立一个就OK了，基于 A 不为空串
                    if (i > 0) {
                        //情况1 没有 . 和 * 那就是直接匹配 A[i-1] = B[j-1] ，继续向前匹配 A[i-2] = B[j-2]
                        boolean one = str.charAt(i - 1) == pattern.charAt(j - 1);
                        //情况2 如果是 . 那就是直接相等了 A[i-1] = B[j-1]，继续向前匹配 A[i-2] = B[j-2]
                        boolean two = pattern.charAt(j - 1) == '.';
                        if (one || two) {
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }
                } else {
                    //碰到 * 了，情况3 ， 处于忽略或者不忽略
                    //忽略，往前面匹配 A[n-1] 没有 c , 那 B 最后2个字符忽略 ，继续向前匹配 A[i-1] = B[j-3]
                    if (j >= 2) {
                        dp[i][j] = dp[i][j - 2];
                    }
                    //不忽略 A[n-1] 中有 c , A中的 c 可以有一个或者多个，继续向前匹配 A[i-2] = B[j-2]
                    // 处理一下边界条件   >= 1 && j >= 2
                    if (i >= 1 && j >= 2) {
                        // a = a* 这种情况
                        boolean one = str.charAt(i - 1) == pattern.charAt(j - 2);
                        // a = .* 这种情况
                        boolean two = pattern.charAt(j - 2) == '.';
                        if (one || two) {
                            //忽略或者不忽略 只要一个符合条件就行了
                            dp[i][j] = dp[i][j] || dp[i - 1][j];
                        }
                    }
                }
            }
        }
        //  dp[A.length][B.length] 就是最后结果
        return dp[n][m];
    }
}

自顶向下实现（部分代码可以写成一行，为了方便解释，分行了）：

import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
       return dp(str, pattern, str.length(), pattern.length());
    }

    HashMap<String, Boolean> memo = new HashMap<>();

    public boolean dp(String str, String pattern, int i, int j) {
        int m = str.length();
        int n = pattern.length();
        // base case
        if (i == 0 && j == 0) {
            return true;
        }
        if (i >= 1 && j == 0) {
            return false;
        }

        // 记录状态 (i, j)，消除重叠子问题
        String key = i + "," + j;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        boolean res = false;
                //状态转义方程
        if (pattern.charAt(j - 1) != '*') {
            if (i > 0) {
                //情况1 没有 . 和 * 那就是直接匹配 A[i-1] = B[j-1] ，继续向前匹配 A[i-2] = B[j-2]
                boolean one = str.charAt(i - 1) == pattern.charAt(j - 1);
                //情况2 如果是 . 那就是直接相等了 A[i-1] = B[j-1]，继续向前匹配 A[i-2] = B[j-2]
                boolean two = pattern.charAt(j - 1) == '.';
                if (one || two) {
                    res = dp(str, pattern, i - 1, j - 1);
                }
            }
        } else {
            //碰到 * 了，情况3 ， 处于忽略或者不忽略
            //忽略，往前面匹配 A[n-1] 没有 c , 那 B 最后2个字符忽略 ，继续向前匹配 A[i-1] = B[j-3]
            if (j >= 2) {
                res = dp(str, pattern, i, j - 2);
            }
            //不忽略 A[n-1] 中有 c , A中的 c 可以有一个或者多个，继续向前匹配 A[i-2] = B[j-2]
            // 处理一下边界条件   >= 1 && j >= 2
            if (i >= 1 && j >= 2) {
                // a = a* 这种情况
                boolean one = str.charAt(i - 1) == pattern.charAt(j - 2);
                // a = .* 这种情况
                boolean two = pattern.charAt(j - 2) == '.';
                if (one || two) {
                    //忽略或者不忽略 只要一个符合条件就行了
                    res = res || dp(str, pattern, i - 1, j);
                }
            }
        }

        // 将当前结果记入备忘录
        memo.put(key, res);
        return res;
    }
}

复杂度分析

时间复杂度：O(MN) ，取决于主串 A 跟模式串 B的长度来确定循环次数
空间复杂度：O(MN) ，取决于主串 A 跟模式串 B的长度来规划大小