给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘‘ 的通配符匹配。’?’ 可以匹配任何单个字符。’‘ 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。
说明:
s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
- 示例 1:
输入:s = “aa” p = “a”
输出: false
- 示例 2:
输入:s = “aa” p = “*”
输出: true
- 示例 3:
输入:s = “cb” p = “?a”
输出: false
- 示例 4:
输入: s = “adceb” p = “ab”
输出: true
解法：
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
| object RegxMatch {
def main(args: Array[String]): Unit = {
println(isMatch("aa", "*"))
println(isMatch("abcd", "a??d"))
}
def isMatch(s: String, p: String): Boolean = {
val dp = new Array[Array[Boolean]](s.length + 1)
for (i <- 0 until dp.length) {
dp(i) = new Array[Boolean](p.length + 1)
}
dp(0)(0) = true
scala.util.control.Breaks.breakable(for (i <- 0 until p.length) {
if (p.charAt(i) == '*') {
dp(0)(i + 1) = true
} else {
scala.util.control.Breaks.break()
}
})
for (i <- 1 until s.length + 1) {
for (j <- 1 until p.length + 1) {
if (p.charAt(j - 1) == '?') {
dp(i)(j) = dp(i - 1)(j - 1)
} else if (p.charAt(j - 1) == '*') {
dp(i)(j) = dp(i - 1)(j) || dp(i)(j - 1)
} else {
if (s.charAt(i - 1) == p.charAt(j - 1)) {
dp(i)(j) = dp(i - 1)(j - 1)
}
}
}
}
dp(s.length)(p.length)
}
}
|