44. 通配符匹配

🔴   🔖  贪心 递归 字符串 动态规划  🔗 力扣 LeetCode

题目

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.
• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"

Output: true

Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"

Output: false

Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

• 0 <= s.length, p.length <= 2000
• s contains only lowercase English letters.
• p contains only lowercase English letters, '?' or '*'.

题目大意

给定一个输入字符串 (s) 和一个模式 (p)，请实现通配符匹配，支持 ? 和 *。

• ? 可以匹配任何单个字符。
• * 可以匹配任意字符串（包括空字符串）。

匹配应该覆盖整个输入字符串（而不是部分匹配）。

解题思路

这个问题可以使用动态规划来解决，具体思路如下：

1. 定义状态：dp[i][j] 表示字符串 s 的前 i 个字符是否能够匹配模式 p 的前 j 个字符。

2. 初始化状态：dp[0][0] 表示空字符串匹配空模式，为 True；dp[i][0] 表示空模式，不管字符串 s 有多长，都为 False。

3. 状态转移方程：

   • 当 p[j-1] 是普通字符且当前字符匹配时，dp[i][j] = dp[i-1][j-1]，表示结果与之前状态相同。

   • 当 p[j-1] 是 '*' 时，dp[i][j] 可以通过以下三种情况获得：

     • 匹配零个字符：dp[i][j] = dp[i][j-1]
     • 匹配一个字符：dp[i][j] = dp[i-1][j-1]
     • 匹配多个字符：dp[i][j] = dp[i-1][j]

4. 最终返回 dp[m][n]，其中 m 和 n 分别是字符串 s 和模式 p 的长度。

复杂度分析

• 时间复杂度： O(m * n)，其中 m 和 n 分别是字符串 s 和模式 p 的长度。
• 空间复杂度： O(m * n)

代码

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
var isMatch = function (s, p) {
	const m = s.length;
	const n = p.length;
	const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(false));

	// 空字符串和空模式匹配
	dp[0][0] = true;

	// 初始化 dp[0][j]，处理 p 中可能出现 '*' 的情况
	for (let j = 1; j <= n; j++) {
		if (p[j - 1] == '*') {
			dp[0][j] = dp[0][j - 1];
		}
	}

	for (let i = 1; i <= m; i++) {
		for (let j = 1; j <= n; j++) {
			if (s[i - 1] == p[j - 1] || p[j - 1] == '?') {
				dp[i][j] = dp[i - 1][j - 1];
			} else if (p[j - 1] == '*') {
				dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 1][j - 1];
			}
		}
	}
	return dp[m][n];
};

相关题目

题号	标题	题解	标签	难度
10	正则表达式匹配	[✓]	递归 字符串 动态规划