给定一个字符串 (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'。示例 4:
输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输出: false解答：
这个真不会官方解答：
1.动态规划
func isMatch(s string, p string) bool {
m, n := len(s), len(p)
dp := make([][]bool, m+1)
for i := 0; i <= m; i++ {
dp[i] = make([]bool, n+1)
}
dp[0][0] = true
for i := 1; i <= n; i++ {
if p[i-1] == '*' {
dp[0][i] = true
} else {
break
}
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
dp[i][j] = dp[i][j-1] || dp[i-1][j]
} else if p[j-1] == '?' || s[i-1] == p[j-1] {
dp[i][j] = dp[i-1][j-1]
}
}
}
return dp[m][n]
}2.贪心算法
func isMatch(s string, p string) bool {
for len(s) > 0 && len(p) > 0 && p[len(p)-1] != '*' {
if charMatch(s[len(s)-1], p[len(p)-1]) {
s = s[:len(s)-1]
p = p[:len(p)-1]
} else {
return false
}
}
if len(p) == 0 {
return len(s) == 0
}
sIndex, pIndex := 0, 0
sRecord, pRecord := -1, -1
for sIndex < len(s) && pRecord < len(p) {
if p[pIndex] == '*' {
pIndex++
sRecord, pRecord = sIndex, pIndex
} else if charMatch(s[sIndex], p[pIndex]) {
sIndex++
pIndex++
} else if sRecord != -1 && sRecord+1 < len(s) {
sRecord++
sIndex, pIndex = sRecord, pRecord
} else {
return false
}
}
return allStars(p, pIndex, len(p))
}
func allStars(str string, left, right int) bool {
for i := left; i < right; i++ {
if str[i] != '*' {
return false
}
}
return true
}
func charMatch(u, v byte) bool {
return u == v || v == '?'
}