描述

题目描述

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

示例

输入："aaa","a*a"
返回值：true

引言

知识点：动态规划，递归，正则表达式
难度：⭐⭐⭐⭐

题解

解题思路

对于动态规划解法，总的思路便是状态转移，即不断判断从 str[:1] 和 pattern[:1] ，即从第一个字符开始判断是否匹配，直到整个字符串完全匹配。

如下图的图解，每次状态转移总共有两种状态：（1）str 增加一个字符，判断是否匹配（2）pattern增加一个字符，判断是否匹配

方法一：动态规划

• 每个字符有三种情况出现：“字符”、”.“、“*”
• 状态定义：dp[i][j]表示字符串 str的前 i 个字符串和 pattern 的前 j 个字符串是否匹配
• 状态转移：主要是对 “*” 的状态处理
  • 当 pattern[i - 1] != “*”，即上一位不为*。dp[i][j]在以下任何一种情况为true时，则等于true
    • 1、dp[i - 1][j - 1] && str[i - 1] == pattern[j - 1]，即上一个状态和当前位的字符都匹配
    • 2、dp[i - 1][j - 1] && pattern[j - 1] == '.'，即上一个状态为true，且pattern上一位包含 ‘.’
  • 当 pattern[i - 1] == “*”，即当前位的上一位为*。dp[i][j]在以下任何一种情况为true时，则等于true
    • 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 次时，能否匹配；
• 状态初始化
  • dp[0][0] == true： 代表两个空字符串能够匹配。
  • dp[0][j] = dp[0][j - 2] 且 p[j - 1] = '*', 即当前pattern的0到j位是true还是false，取决于dp[0][j-2]是否匹配，以及 pattern的当前位的上一位是否为‘*’，因为‘*’可以匹配任何值，包括空值
• 返回值
  • dp 矩阵右下角字符，代表字符串 str 和 pattern 能否匹配。

图解

算法流程：

• 定义状态，并初始化
• 遍历每个str和pattern中的字符
  • 1、当比较的位pattern[j-1]=='.', 或者字符相等匹配,则状态取决于上一次状态
  • 2、对于包含 * 的匹配
    • 当之前位为 '.', 或者字符相等,则匹配
    • 否则只能不匹配
• 返回状态转移最后的结果

Java 版本代码如下：

import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
        int strLen = str.length() + 1, patternLen = pattern.length() + 1;
        // 定义状态，并初始化
        boolean[][] dp = new boolean[strLen][patternLen];
        dp[0][0] = true;
        // 初始化首行
        for(int j = 2; j < patternLen; j++) {
            // 因为pattern[j-1]的 * 可以取任意值包括空值,因此dp[0][j]相当于取决于dp[0][j-2]
            if(pattern.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }
        // 状态转移
        for(int i = 1; i < strLen; i++) {
            for(int j = 1; j < patternLen; j++) {
                // 当比较的位pattern[j-1]=='.', 或者字符相等匹配,则状态取决于上一次状态
                if (pattern.charAt(j - 1) == '.' || str.charAt(i - 1) == pattern.charAt(j - 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[strLen - 1][patternLen - 1];
    }
}

Python 版本代码如下：

class Solution:
    def match(self, s, p):
        if not s and not p:
            return True
        m, n = len(s) + 1, len(p) + 1  # 两个字符串的长度
        dp = [[False] * n for i in range(m)]
        # 初始化
        dp[0][0] = True
        for j in range(2, n, 2):
            dp[0][j] = dp[0][j - 2] and p[j - 1] == '*'
        # 状态转移
        for i in range(1, m):
            for j in range(1, n):
                if p[j - 1] == '*':
                    if dp[i][j - 2]: dp[i][j] = True
                    elif dp[i - 1][j] and s[i - 1] == p[j - 2]: dp[i][j] = True
                    elif dp[i - 1][j] and p[j - 2] == '.': dp[i][j] = True
                else:
                    if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]: dp[i][j] = True
                    elif dp[i - 1][j - 1] and p[j - 1] == '.': dp[i][j] = True
        return dp[-1][-1]

复杂度分析：

时间复杂度 O(SP)：其中 S，P 分别为 str 和 pattern 的长度，状态转移需遍历整个 dp 矩阵
空间复杂度 O(SP)：状态二维矩阵 dp