剑指 Offer 19: 正则表达式匹配

[songyy5517]

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

示例 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

• s可能为空，且只包含从a-z的小写字母。
• p可能为空，且只包含从a-z的小写字母以及字符 .和 *，无连续的'*'。

分析 这道题考察的是字符串匹配。不同长度的字符串可以看成是不同的状态，因此字符串匹配涉及到状态之间的转移，所以我们可以考虑使用动态规划来解决问题。

[songyy5517]

思路1：动态规划

1. 定义二维布尔数组 f，f[i][j] 表示字符串 s 的前 i 个字符与正则表达式 p 的前 j 个字符是否匹配

2. 初始化 & 考虑特殊情况：当正则表达式为空时， (1) 若字符串为空，则二者匹配，即 f[0][0] = true; (2) 若字符串非空，则二者不匹配，即 f[i][0] = false (i≠0);

3. 匹配字符串 s 与正则表达式 p，即需要计算出 f[s.length()][p.length()] 的值，因此我们需要从 f[0][0] 出发计算每个 f 中的值。根据正则表达式 p 的当前（位置j）字符是否为 '*', 有两种不同的匹配情况： (1) 若 p 当前（位置j）字符不为 '*'，则直接对比 p 与 s （位置i）当前的字符是否匹配；

   • 若匹配，则看二者之前的串是否匹配，即 f[i][j] = f[i-1][j-1];
   • 若不匹配，则二者匹配失败。

   (2) 若 p 当前（位置j）字符为 '*'，则分两种情况：

   • 若 p 中 '*' 前一个字符（位置j-1）与 s 的当前字符（位置i）匹配，则继续看 s 前一个字符是否也匹配，即 f[i][j] = f[i-1][j];
   • 不管 p 中 '*' 前一个字符（位置j-1）与 s 的当前字符（位置i）匹不匹配，直接跳过 p 中的'*'组合，即 f[i][j] = f[i][j-2]。
   • 若上述两种情况中，存在一种匹配成功的情况，则 s 和 p 在当前位置下可以匹配成功！

4. 返回最终的匹配结果 f[s_len][p_len]

复杂度分析

• 时间复杂度： $O(MN)$ ， $M, N$ 分别表示字符串和正则表达式的长度，算法需要计算 $M\times N$ 个状态的值；
• 空间复杂度： $O(MN)$ ，我们额外定义大小为 $M\times N$ 的Boolean二维数组，用来存放各个状态。

[songyy5517]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        // 分析：动态规划
        // 1. 异常处理
        if (str == null || pattern == null)
            return false;

        // 2. 状态定义&初始化
        // f[i][j]: str[0:i]能否与pattern[0:j]匹配成功
        // f[i][0]一定为false (i!=0)
        boolean[][] f = new boolean[str.length() + 1][pattern.length() + 1];
        f[0][0] = true;

        // 3. 自底向上计算各个状态
        for (int i = 0; i < str.length() + 1; i++){
            for (int j = 1; j < pattern.length() + 1; j++){
                // 正则表达式的当前字符不为'*'
                if (pattern.charAt(j - 1) != '*'){
                    // 当前字符匹配成功，则进行状态转移
                    if (i > 0 && (pattern.charAt(j-1) == str.charAt(i - 1) || pattern.charAt(j-1) == '.'))
                        f[i][j] = f[i-1][j-1];  

                    // 不匹配，则将状态值置为false
                    else
                        f[i][j] = false;  
                }

                // 正则表达式的当前字符为'*'
                else {
                    // 无论匹配与否，直接跳过'*'组合
                    if (j >= 2)
                        f[i][j] = f[i][j-2];

                    // 匹配'*'组合
                    if (j >= 2 && i >= 1 && (pattern.charAt(j-2) == '.' || pattern.charAt(j-2) == str.charAt(i-1)))
                        f[i][j] = f[i-1][j] || f[i][j];
                }
            }
        }

        return f[str.length()][pattern.length()];
    }
}

[songyy5517]

思路2：递归

1. 递归出口：
   • 字符串 s 和正则表达式 p 都为空串 "" 时，表示匹配成功，返回true；
   • s 不为空，p为空，则匹配失败，返回false；

2. 按从后往前的顺序，依次匹配 s 和 p：[递归] (1) 若 p 当前字符不为 '*'，比较 s 与 p 的当前字符是否匹配：

   • 若匹配，则看二者之前的字符串是否匹配，即返回 isMatch(s.substring(0, s_len-1), p.substring(0, p_len-1))
   • 若不匹配，则直接返回false。

   (2) 若 p 当前字符为 '*'，则看 p 的前一个字符是否可与 s 的当前字符匹配：

   • 若匹配，则继续看 s 的前一个字符，且还要考虑跳过'*'组合的情况，即返回 isMatch(s.subsring(0, s_len-1), p) || isMatch(s, p.substring(0, p_len-2))；
   • 若不匹配，则直接跳过'*'组合，即返回 isMatch(s, p.substring(0, p_len-2))；
3. 若不满足上述情况，则返回false

[songyy5517]

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
        // 分析：递归，自顶向下匹配字符串

        // 递归出口
        if (str.equals("") && pattern.equals(""))
            return true;
        if (!str.equals("") && pattern.equals(""))
            return false;

        // 正则表达式当前字符不为'*'
        int p_len = pattern.length();
        int s_len = str.length();

        // 正则表达式当前字符不为'*'
        if (pattern.charAt(p_len-1) != '*'){
            if (s_len > 0 && (pattern.charAt(p_len-1) == '.' || pattern.charAt(p_len-1) == str.charAt(s_len-1)))
                return match(str.substring(0,s_len-1), pattern.substring(0, p_len-1));
            else
                return false;
        }

        // 正则表达式当前字符为'*'
        else{
            // 匹配'*'组合：匹配||直接跳过
            if (p_len > 1 && s_len > 0 && (pattern.charAt(p_len - 2) == str.charAt(s_len-1) || pattern.charAt(p_len - 2) == '.'))
                return match(str.substring(0,s_len-1), pattern) || match(str, pattern.substring(0,p_len-2));

            // 没有匹配成功则直接跳过'*'组合
            return match(str, pattern.substring(0, p_len-2));
        }
    }
}

[songyy5517]

2023/1/31

1. 在动态规划中，需要设置双层循环对boolean二维数组的所有元素进行计算，方向是自下而上；递归则是自上而下。
2. 递归的终止条件：比较两个字符串
3. 判断条件一定要考虑下标的范围是否合格

2023/2/1

1. 动态规划：主分支应该是p当前字符是否为'*'，而不能是 i > 0

2023/11/27

1. 字符匹配类型的题目则可以使用动态规划；
2. 以当前字符是否为 * 划分匹配情况；
3. 遇到*组合时，可以选择直接跳过。

2023/11/29

1. 范围判断需放在条件语句的开始：if (i > 0 && (cur_p == '.' || cur_p == str.charAt(i - 1))) 而不是：if (cur_p == '.' || (i > 0 && cur_p == str.charAt(i - 1)))

2024/3/23 2024/4/5