LeetCode 剑指 Offer 19. 正则表达式匹配

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

✅ 剑指 Offer 19. 正则表达式匹配

思路分析

解法一：动态规划（推荐）

核心思路：

设 dp[i][j] 表示 s[0..i) 与 p[0..j) 是否匹配。

若 p[j-1] 不是 *：

当前字符匹配且 dp[i-1][j-1] 为真。

若 p[j-1] 是 *：

视为出现 0 次：dp[i][j] = dp[i][j-2]

或出现 >=1 次：若 s[i-1] 与 p[j-2] 匹配，则 dp[i][j] |= dp[i-1][j]

复杂度分析：

时间复杂度：O(mn)，其中 m、n 分别为字符串与模式长度。

空间复杂度：O(mn)。

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        for (int j = 2; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 2];
            }
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char pc = p.charAt(j - 1);
                if (pc != '*') {
                    if (matches(s.charAt(i - 1), pc)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    }
                } else {
                    dp[i][j] = dp[i][j - 2];
                    char prev = p.charAt(j - 2);
                    if (matches(s.charAt(i - 1), prev)) {
                        dp[i][j] |= dp[i - 1][j];
                    }
                }
            }
        }

        return dp[m][n];
    }

    private boolean matches(char sc, char pc) {
        return pc == '.' || sc == pc;
    }
}

func isMatch(s string, p string) bool {
	m, n := len(s), len(p)
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	dp[0][0] = true

	for j := 2; j <= n; j++ {
		if p[j-1] == '*' {
			dp[0][j] = dp[0][j-2]
		}
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			pc := p[j-1]
			if pc != '*' {
				if matchChar(s[i-1], pc) {
					dp[i][j] = dp[i-1][j-1]
				}
			} else {
				dp[i][j] = dp[i][j-2]
				prev := p[j-2]
				if matchChar(s[i-1], prev) {
					dp[i][j] = dp[i][j] || dp[i-1][j]
				}
			}
		}
	}

	return dp[m][n]
}

func matchChar(sc byte, pc byte) bool {
	return pc == '.' || sc == pc
}

相似题目

题目	难度	考察点
10. 正则表达式匹配	困难	动态规划
44. 通配符匹配	困难	动态规划
97. 交错字符串	中等	动态规划
72. 编辑距离	困难	动态规划
115. 不同的子序列	困难	动态规划
139. 单词拆分	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/12988325