看到这道题，首先想到的就是 正则匹配 Regular Expression Matching 一节中的方法，即使进行了一些剪枝操作（去除重复的*），但还是超时了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func testMatch(s []byte, p []byte) bool {
if len(p)==0 {
return len(s)==0
}
switch {
case len(s)>0 && (s[0]==p[0] || p[0]=='?'):
return testMatch(s[1:],p[1:])
case p[0]=='*':
i:=0
for ;i<len(p) && p[i]=='*';i++ {}
if len(s)>0 {
return testMatch(s[1:],p) || testMatch(s,p[i:])
}else{
return testMatch(s,p[i:])
}
default:
return false
}
}
func isMatch(s string, p string) bool {
return testMatch([]byte(s),[]byte(p))
}
|
接下来准备用 DP 试试。
使用递归版本的 DP，果然没有 timeout。
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
| var (
dp [][]int
gs string
gp string
)
func testMatch(i,j int) bool{
if dp[i]==nil {
dp[i]=make([]int,len(gp)+1)
}
if dp[i][j]==0 {
ans:=false
if j==len(gp) {
ans=i==len(gs)
}else{
if i<len(gs) && (gs[i]==gp[j] || gp[j]=='?') {
ans=testMatch(i+1,j+1)
}else if gp[j]=='*' {
t:=0
for ;j+t<len(gp) && gp[j+t]=='*';t++ {}
if i<len(gs) {
ans=testMatch(i+1,j) || testMatch(i,j+t)
}else{
ans=testMatch(i,j+t)
}
}else{
ans=false
}
}
if ans {
dp[i][j]=1
}else{
dp[i][j]=2
}
}
if dp[i][j]==1 {
return true
}
return false
}
func isMatch(s string, p string) bool {
dp=make([][]int,len(s)+1)
gs,gp=s,p
return testMatch(0,0)
}
|
当然，也可以使用循环版本的 DP，他们的复杂度都是 O(m*n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func isMatch(s string, p string) bool {
dp:=make([][]bool,len(s)+1)
for i:=0;i<=len(s);i++ {
dp[i]=make([]bool,len(p)+1)
}
dp[len(s)][len(p)]=true
for i:=len(s);i>=0;i-- {
for j:=len(p)-1;j>=0;j-- {
if i<len(s) && (s[i]==p[j] || p[j]=='?') {
dp[i][j]=dp[i+1][j+1]
}else if p[j]=='*' {
dp[i][j]=dp[i][j+1]
if i<len(s){
dp[i][j]=dp[i][j]||dp[i+1][j]
}
}else{
dp[i][j]=false
}
}
}
return dp[0][0]
}
|
看到了 Discuss 中的一个解法，非常有意思，它的思路独特，并且将空间复杂度降低为常数。
它的特色就是如果在 pattern 中遇到*，就记录*的位置。然后，先尝试跳过*进行匹配，如果匹配失败，再读取原来的位置，并尝试跳过 string 中的一个字符，继续匹配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| func isMatch(s string, p string) bool {
idS,idP:=0,0
saveS,saveP:=-1,0
for idS<len(s) {
if idP<len(p) && (s[idS]==p[idP] || p[idP]=='?') {
idS++
idP++
}else if idP<len(p) && p[idP]=='*' {
saveS=idS
saveP=idP
idP++
}else if saveS!=-1 {
saveS++
idS=saveS
idP=saveP+1
}else{
return false
}
}
for ;idP<len(p) && p[idP]=='*';idP++{}
return idP==len(p)
}
|