来源:力扣 (LeetCode)
链接:https://leetcode-cn.com/problems/wildcard-matching
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。
- '?' 可以匹配任何单个字符。
- '*' 可以匹配任意字符串 (包括空字符串) 。
两个字符串完全匹配才算匹配成功。
说明:
- s 可能为空,且只包含从 a-z 的小写字母。
- p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。
示例 1:
- 输入:s = "aa", p = "a"
- 输出:false
- 解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
- 输入:s = "aa", p = "*"
- 输出: true
- 解释: '*' 可以匹配任意字符串。
示例 3:
- 输入:s = "cb", p = "?a"
- 输出:false
- 解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
二、题解
动态规划,使用 dp[i][j]
表示字符串 s 的第 i 个字符和模式串 p 的第 j 个字符的匹配状况,如果匹配上了设置为 true,否则为 false 。
dp[i][j]
何时为 true:
- 当
s[i] == p[j]
或者p[j] == '?'
的时候,只要两个字符串前面的字符匹配上 (也就是dp[i - 1][j - 1] = ture
),那么这里的两个字符也匹配上。 - 当
s[i] == '*'
的时候,有两种情况能匹配上:- 模式串 p 的前面一个字符已经匹配上字符串 s 了,如
s=ab, p=ab*
,相当于dp[i][j - 1] = true
时,能继续匹配。 - 字符串 s 的前面一个字符已经匹配上 p 了,此时模式串可以继续匹配。如
s=abcd, p=ab*
,相当于dp[i - 1][j] = true
时,能继续匹配。 - 注意这里的状态并不是
d[i - 1][j - 1]
控制的,因为一个*
可以匹配多个字符,而?
只能匹配一个字符。
- 模式串 p 的前面一个字符已经匹配上字符串 s 了,如
初始情况下:
dp[0][0] = true
:空字符串 s 和空字符 p,匹配上。dp[0][j]
:s 为空,p 不为空,只有 p 是*
时值才为 true 。dp[i][0]
:s 不为空,p 为空,永远不可能匹配上,都是 false 。
基于以上几点,就可以写出代码了。
三、代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
bool isMatch(string s, string p) { int i, j; vector<vector<bool>> dp(s.length() + 1, vector<bool>(p.length() + 1, false)); // 初始化数组 dp[0][0] = true; for (j = 1; j <= p.length(); j++) { if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1]; else break; } for (i = 1; i <= s.length(); i++) { for (j = 1; j <= p.length(); j++) { if ((s[i - 1] == p[j - 1] || p[j - 1] == '?')) dp[i][j] = dp[i - 1][j - 1]; if (p[j - 1] == '*' && (dp[i - 1][j] || dp[i][j - 1])) { dp[i][j] = true; } } } return dp[s.length()][p.length()]; } |
评论