*代表任意长度的任意字符
?代表任意字符
需要实现这个匹配逻辑。现在有字符串s和匹配模版p，要求判断p是否能完全匹配s
思路
从左到由遍历p，可以这样匹配
- 如果该字符为固定字符，就能找到这个字符在s中的所有下标
- 如果该字符为*，匹配任意长度0-MAX
- 如果该字符为?，匹配任意长度1
优化一下
** = * ⇒ 匹配长度 0-MAX
*? = ?* ⇒ 匹配长度1-MAX
ab ⇒ 满足s.indexOf(a)+1 = s.indexOf(b)
a?b ⇒ 满足s.indexOf(a)+2 = s.indexOf(b)
a???b ⇒ 满足s.indexOf(a)+4 = s.indexOf(b)
a*b ⇒ 满足s.indexOf(a) ≤ s.indexOf(b)
a?b = a?b ⇒ 满足s.indexOf(a)+1 ≤ s.indexOf(b)
除了*，其他字符串都是长度固定的，所以我们可以将p视为用*连接的多个子字符串
str1*str2*str3*str4
需要满足，
- s.indexOf(str1)≤s.indexOf(str2)≤s.indexOf(str3)≤s.indexOf(str4)
- len(str1)+len(str2)+len(str3)+len(str4) ≤ len(s)
再经过一点点小优化，就成了这样子：
func isMatch(s string, p string) bool {
isChar := true
maybe := []int{-1}
limit := 1
for i:= range p {
switch p[i] {
case '*':
isChar = false
case '?':
limit++
default:
if isChar {
index := 0
for _, loc := range maybe {
if loc+limit < len(s) && s[loc+limit] == p[i] {
maybe[index] = loc
index++
}
}
maybe = maybe[:index]
limit++
} else {
from := maybe[0] + limit
maybe = maybe[:0]
for j := from; j < len(s); j++ {
if s[j] == p[i] {
maybe = append(maybe, j)
}
}
limit = 1
}
isChar = true
}
//fmt.Printf("%v -> ", maybe)
if len(maybe) == 0 {
return false
}
}
if isChar {
for _, try := range maybe {
if try+limit == len(s) {
return true
}
}
return false
} else {
return maybe[0]+limit <= len(s)
}
}