1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| // @lc code=start
impl Solution {
/// ## 解题思路
/// 1. 动态规划
/// 2. 递归
pub fn is_match(s: String, p: String) -> bool {
/// - 递归
fn _is_match_rec(s: &[u8], p: &[u8]) -> bool {
match (p, s) {
([], _) => s.is_empty(),
([a, ..], []) => *a == b'*' && _is_match_rec(s, &p[1..]),
([b'?', ..], _) => _is_match_rec(&s[1..], &p[1..]),
([b'*', ..], _) => _is_match_rec(&s[1..], p) || _is_match_rec(s, &p[1..]),
([a, ..], [b, ..]) if a == b => _is_match_rec(&s[1..], &p[1..]),
_ => false,
}
}
/// - 动态规划
fn _is_match_dp(s: &[u8], p: &[u8]) -> bool {
let mut dp = vec![vec![false; p.len() + 1]; s.len() + 1];
dp[0][0] = true;
// s为空时
for i in 0..p.len() {
dp[0][i + 1] = dp[0][i] && p[i] == b'*'
}
for i in 0..s.len() {
for j in 0..p.len() {
dp[i + 1][j + 1] = match p[j] {
b'?' => dp[i][j], //'?'匹配任意单字符
b'*' => dp[i + 1][j] || dp[i][j + 1], //'*'匹配0次或多次任意字符
a => a == s[i] && dp[i][j], //普通字符
}
}
}
dp[s.len()][p.len()]
}
//_is_match_rec(s.as_bytes(), p.as_bytes())
_is_match_dp(s.as_bytes(), p.as_bytes())
}
}
// @lc code=end
struct Solution;
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test() {
assert_eq!(Solution::is_match("adceb".to_string(), "*a*b".into()), true);
}
}
|