Skip to content

Latest commit

 

History

History
135 lines (99 loc) · 4.01 KB

0044.md

File metadata and controls

135 lines (99 loc) · 4.01 KB
title description keywords
44. 通配符匹配
LeetCode 44. 通配符匹配题解，Wildcard Matching，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
44. 通配符匹配
通配符匹配
Wildcard Matching
解题思路
贪心
递归
字符串
动态规划

44. 通配符匹配

🔴 Hard  🔖  贪心 递归 字符串 动态规划  🔗 力扣 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 正则表达式匹配 [✓] 递归 字符串 动态规划 🔴 🀄️ 🔗