通配符匹配

Tips

题目类型: Dynamic Programming

题目

给定一个字符串 s 和一个字符模式 p, 实现一个支持 '?' 和 '*' 的通配符匹配. 两个字符串完全匹配才算匹配成功.

'?' 可以匹配任何单个字符.
'*' 可以匹配任意字符串(包括空字符串).

说明:

s 可能为空, 且只包含从 a-z 的小写字母.
p 可能为空, 且只包含从 a-z 的小写字母, 以及字符 ? 和 *.

示例

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串.

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串.

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'.

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

输入: s = 'acdcb'
p = 'a*c?b'
输出: false

题解

状态定义

dp[i][j] 表示 s 的前 i 个字符和 p 的前 j 个模式字符是否匹配.

状态转移

如果 p[j - 1] === s[i - 1] 或 p[j - 1] === '?', 表示当前的字符串是匹配的, dp[i][j] 可以从 dp[i - 1][j - 1] 转移而来.
如果 p[j - 1] === '*', 这个位置可以匹配 0 到若干个字符. 那么 dp[i][j] 可以从 dp[i - 1][j] 转移而来(表示当前星号没有匹配字符); 也可以从 dp[i][j - 1] 转移而来(表示当前星号匹配了当前的位置的字符). 因为只要任意一种匹配即可, 所以这里是或的关系.

初始条件

dp[0][0] = true 表示空串是匹配的.
当 p 以若干个星号开头时, 可以匹配到空字符串(即 i 为 0), 因为星号是可以匹配空串的.

JavaScript
Rust

/**
 * @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(false)
    .map(() => new Array(n + 1).fill(false))

  dp[0][0] = true
  for (let j = 1; j <= n; j++) {
    if (p[j - 1] === '*') {
      dp[0][j] = true
    } else {
      break
    }
  }

  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 - 1][j] || dp[i][j - 1]
      }
    }
  }

  return dp[m][n]
}

pub fn is_match(s: String, p: String) -> bool {
    let (m, n) = (s.len(), p.len());
    let (s_bytes, p_bytes) = (s.as_bytes(), p.as_bytes());
    let mut dp = vec![vec![false; n + 1]; m + 1];

    dp[0][0] = true;
    for j in 1..=n {
        match p_bytes[j - 1] == b'*' {
            true => dp[0][j] = true,
            false => break,
        }
    }

    for i in 1..=m {
        for j in 1..=n {
            if s_bytes[i - 1] == p_bytes[j - 1] || p_bytes[j - 1] == b'?' {
                dp[i][j] = dp[i - 1][j - 1];
            } else if p_bytes[j - 1] == b'*' {
                dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
            }
        }
    }

    dp[m][n]
}

题目​

题解​

状态定义​

状态转移​

初始条件​

题目

题解

状态定义

状态转移

初始条件