10.正则表达式匹配.md

10.正则表达式匹配

题目

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

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

示例 1：

输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3：

输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

输入：s = "mississippi" p = "mis*is*p*."
输出：false

来源：力扣（LeetCode）

思路与解答

本题有两种解法，直接递归和动态规划，先说递归，最重要的是需要分类讨论，原串定义为str,模式串为pattern。

• 如果pattern长度为0
  • 且str长度为0,说明刚刚好匹配完，返回ture
  • str长度不为0，说明没有匹配完，返回false
• 如果pattern的长度大于0
  • 如果pattern的长度大于1，且第2个字符是*，说明前面的字符可以匹配0，1或者多次
    • 分为两种情况讨论，一种是直接把*和*前面的字符去掉，相当于匹配了0个，然后接着比较；另外一种是，如果str的长度大于0，并且第一个字符匹配，那就把str的第一个字符去掉，两者接着匹配。
  • 否则，说明第二个字符不是*，那么就直接比较第一个字符是不是匹配，同时将后面的字符进行匹配。

注意：上面说的第一个字符是不是匹配，除了两个字符相等的情况，其实还有模式串的字符为'.'的情况。

class Solution {
    public boolean isMatch(String str, String pattern) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        // 第二个字符是'*'
        if (pattern.length() > 1 && pattern.charAt(1) == '*') {
            // 匹配0次，直接把'*'去掉，两者判断
            return isMatch(str, pattern.substring(2)) 
            // 第一个字符相同的时候，去掉第一个字符，判断后面的（相当于匹配多次）
            || (str.length() > 0 && firstSame(str, pattern)) && isMatch(str.substring(1), pattern);
        } else {
            // 第二个字符不是 '*'的时候，判断第1个字符是否相同，相同的时候再从第2位开始比较
            return str.length() > 0 
                    && firstSame(str, pattern) 
                    && (isMatch(str.substring(1), pattern.substring(1)));
        }
    }

    // 判断第一个字符是不是相同
    private boolean firstSame(String s, String p) {
        // 两个相同，或者有一个是"."
        return s.charAt(0) == p.charAt(0) || p.charAt(0) == '.';
    }
}

当然，这种做法不是最优的，使用了大量的递归操作，并且重复递归，时间复杂度比较高。

现在来看动态规划的做法，虽然过程咋一看有点复杂，我们可以来分析一下，主要思路是动态规划：

1. 首先我们需要定义状态：用一个二维数组（套路）dp[i][j]用来表示str的前i个字符和pattern的前j个字符是否匹配。

2. 接下来，我们需要初始化简单状态，因为想要求后面的状态，是依赖于前面的状态的，一般是初始化dp[i][j]的首行和首列。

   • dp[0][0]= true,表示两个空的字符串是匹配的。
   • dp数组的首列，除了dp[0][0]为true，其他的都是false。因为pattern为空，但是s不为空的时候，肯定不匹配。
   • dp的首行，也就是str为空的时候，如果pattern的偶数位都是“*”,那么就可以匹配，因为可以选择匹配0次。

3. 初始化前面之后，后面的从索引1开始匹配：

   • 1. pattern的第j个字符为“*”(即是 pattern[j-1]=='*')
     • 1.1 如果dp[i][j-2]==true，那么dp[i][j]=true(相当于str的前i和pattern的前j-2个字符匹配，此时的*前面的那个字符出现了0次)。
     • 1.2 如果dp[i-1][j]==true且str[i-1]==pattern[j-2]，则dp[i][j] =true。（如果str的前i - 1个字符和pattern的前j个字符匹配，并且str的第i个字符和pattern的第j - 1个字符相等,相当于‘*’前面的字符出现了1次）
     • 1.3 如果dp[i-1][j]=true且pattern[j-2]=='.'的时候，则dp[i][j]=true。(表示str的前i-1个和patten的前j个匹配，并且pattern的第j-1个是‘.’，第j个是‘*’,那么说明可以匹配任何字符任何次数，自然str可以多匹配一个字符。)
   • 2. pattern的第j个字符不为“*”(即是pattern[j-1]！='*')
     • 2.1 如果dp[i - 1][j - 1]=true and str[i - 1] == pattern[j - 1]时，则dp[i][j]=true。（也就是前面匹配，接下来的字符一样匹配）
     • 2.2 如果dp[i - 1][j - 1]=true且pattern[i-1]=='.'，那么dp[i][j]=true。(其实也是.可以匹配任何字符)

处理完数组之后，最后返回dp[n-1][m-1]，也就是str的前n个和pattern的前m个字符是否匹配。

class Solution {
  public boolean isMatch(String str, String pattern) {
        if (pattern.length() == 0) {
            return str.length() == 0;
        }
        int n = str.length() + 1;
        int m = pattern.length() + 1;
        boolean[][] dp = new boolean[n][m];
        dp[0][0] = true;
        for (int j = 2; j < m; j = j + 2) {
            if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (pattern.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]
                            || dp[i - 1][j] && (str.charAt(i - 1) == pattern.charAt(j - 2)
                            || pattern.charAt(j - 2) == '.');
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i - 1) == pattern.charAt(j - 1)
                            || pattern.charAt(j - 1) == '.');
                }

            }
        }
        return dp[n - 1][m - 1];
    }
}

时间复杂度 O(mn) ： 其中 m,n 分别为 str 和 pattern 的长度，状态转移需遍历整个 dp 矩阵。 空间复杂度 O(mn)： 状态矩阵 dp 使用 O(mn)的额外空间。