题目描述：
给定一个字符串 (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 = "ab"
输出: true
解释: 第一个 '' 可以匹配空字符串, 第二个 '' 可以匹配字符串 "dce". - 示例 5:
输入:
s = "acdcb"
p = "a*c?b"
输入: false
思路一：
- 直接比较两者是否相等；
- 如果不想等，判断是否长度相等且不含*，如果含？，遍历每个字符比较，字符相等，或者是？，反之则为不匹配；不含？，不匹配；
- 如果含有，则以为界限，分为多个字符串，然后每个子字符串去跟对应剩余未匹配过的字符串匹配，如果都匹配，则整个匹配，如果一个不匹配，则都不匹配；
- 如果不包含，则肯定不匹配。 时间复杂度：最大O(nm)
func isMatch(_ s: String, _ p: String) -> Bool {
if s == p { ///直接比较，相等，返回
return true
}else{///不想等，则可能含有其他特殊符号？、 *等
if s.count == p.count && !p.contains("*"){///长度相等，且不含有*，则含有？
if p.contains("?") {
for i in 0..<p.count {///遍历比较
let index = s.index(s.startIndex, offsetBy: i)
if s[index] != p[index] && p[index] != "?" {///比较原则，如果每个字符不想等，且不是？，则不匹配
return false
}
}
return true
}else{///不含？，肯定不匹配
return false
}
}else{///长度不想等或者含有*，如果不含*，这种情况肯定不匹配
if p.contains("*") {///含有*
let strings = p.components(separatedBy: "*")///将字符串以*隔开的子字符串组成的数组
var tempStrings = strings
tempStrings.removeAll(where: {$0 == ""})
if tempStrings.count == 0{//////如果只含有空字符串，则说明只有*，肯定匹配
return true
}
var startCompare = 0///开始比较的位置，接着上一次比较
var k = 0
var isStartFirst = false///是否以*开头
for compoment in strings{///遍历子字符串组成的数组比较
if startCompare + compoment.count > s.count {///开始比较的位置+剩余比较的长度>s.count，肯定不匹配
return false
}
if compoment.count == 0{///空字符，说明以*开头，或者结尾
if k == 0{///以*开头，标记
isStartFirst = true
}
if k == strings.count - 1 {///以*结尾，走到这里，说明前面的已经匹配，*肯定匹配
return true
}
k += 1
continue
}
if k > 0 && k == strings.count - 1 { ///如果子字符串的数量不等于一，则最后一个子字符串需要跟最后对应的子字符串匹配
startCompare = s.count - compoment.count
}
var temps = s
if startCompare != 0{///剔除掉已经比较了的字符串
let startI = s.index(s.startIndex, offsetBy: startCompare - 1)
temps.removeSubrange(s.startIndex...startI)
}
if !(temps.contains(compoment)){///剩余未匹配的字符串，不包含子字符串
if compoment.contains("?") {///如果包含？
for i in startCompare..<s.count{///遍历比较，比较原则，字符不想等，且不为？，则不匹配，更新开始比较的位置，继续比较
var isMatch = true
for j in 0..<compoment.count{
if i + j > s.count - 1{
return false
}
let sindex = s.index(s.startIndex, offsetBy: i+j)
let cindex = compoment.index(compoment.startIndex, offsetBy: j)
if compoment[cindex] != s[sindex] && compoment[cindex] != "?"{
if i >= s.count - compoment.count || (!isStartFirst && startCompare == 0) {///如果是第一组，且不是以*开头，则肯定不匹配；如果是最后一组，也肯定不匹配
return false
}
isMatch = false///不匹配，跳出循环
break
}
}
if isMatch {///匹配到，更新开始匹配位置，跳出循环
startCompare = i + compoment.count
break
}
}
}else{///如果不包含？，肯定不匹配
return false
}
}else{///剩余未匹配的字符串，包含子字符串，查询位置
let range = temps.range(of: compoment)
if startCompare == 0 && !isStartFirst{///第一组，且不以*开头
let lower = temps.distance(from: s.startIndex, to: range!.lowerBound)
if lower != 0{///匹配到的位置不是0，则肯定不匹配
return false
}
}
let up = range!.upperBound
startCompare += temps.distance(from: s.startIndex, to: up)///更新开始匹配的位置
}
k += 1
}
return true
}else{///不含*，肯定不匹配
return false
}
}
}
}
思路二：动态规划
- 概念
- dp[i][j]表示s到i位置,p到j位置是否匹配!
- dp[0][0]:什么都没有,所以为true
- 第一行dp[0][j],换句话说,s为空,与p匹配,所以只要p开始为*才为true
- 第一列dp[i][0],当然全部为False
- 动态方程:
- 如果(s[i-1] == p[j-1] || p[j-1] == "?") && dp[i-1][j-1] ,有dp[i][j] = true
- 如果p[j-1] == "" && (dp[i-1][j] = true || dp[i][j-1] = true)有dp[i][j] = true
note:
dp[i][j-1],表示代表是空字符,例如ab,ab*
dp[i-1][j],表示代表非空任何字符,例如abcd,ab
代码如下：
static func isMatch(_ s: String, _ p: String) -> Bool{
if s == p {
return true
}
if p == "" {
return false
}
let sLength = s.count
let pLength = p.count
var dp :[[Bool]] = Array(repeating: Array(repeating: false, count: pLength + 1), count: sLength + 1)
dp[0][0] = true///全部为空，匹配
let sArray = Array(s)
let pArray = Array(p)
for i in 1...pLength{///*与任意字符匹配
if pArray[i-1] == "*"{
dp[0][i] = dp[0][i-1]
}
}
if sLength < 1{
return dp[sLength][pLength]
}
for i in 1...sLength{
for j in 1...pLength {
if sArray[i-1] == pArray[j-1] || pArray[j-1] == "?"{///i，j位置相等或者是？，若想都匹配，则i-1，j-1位置必须匹配，否则不匹配
dp[i][j] = dp[i-1][j-1]
}else if pArray[j-1] == "*"{///为* i，j位置匹配，若想都匹配，则i-1，j位置必须匹配，或者则i，j-1位置必须匹配，否则不匹配
dp[i][j] = dp[i-1][j] || dp[i][j-1]
}
}
}
return dp[sLength][pLength]
}
参考：通配符匹配
网友评论