LeetCode44-通配符匹配（Golang）

LeetCode-44：通配符匹配

题意：

        有字符串s，和模式串p，规定匹配规则如下：

1. 模式串 p 中的 '*' ，可以与 s 中任意长度的任意字符匹配
2. 模式串 p 中的 '?' ，可以与 s 中的一个任意字符匹配

        判断给定的 s 和 p 能否匹配

思路：

• 利用动态规划进行求解
  • 令 dp[i][j] 表示 s 中前 i 个字符与 p 中前 j 个字符是否匹配
  • 若 p[j] == '?' 或 p[j]==s[i]，则用：dp[i][j]==dp[i-1][j-1]，表示可以匹配
  • 若 p[j] == '*'，因为 '*' 可以匹配多个字符，则用 dp[i][j]==dp[i-1][j] || dp[i][j-1]，进行转移，用 dp[i-1][j] ，就表示占用一个 '*' 用于匹配，用 dp[i][j-1] ，就表示用了星号进行匹配，但是星号依然保留，以便用于匹配后续字符。（重要）

代码（Golang）：

func isMatch(s string, p string) bool {    var dp [][]bool=make([][]bool,len(s)+1)    for i:=0;i<=len(s);i++{ dp[i]=make([]bool,len(p)+1) dp[i][0]=false    }    dp[0][0]=true    for i:=0;i<len(p);i++{ if p[i]=='*'{     dp[0][i+1]=true }else{     break }    }    for i:=0;i<len(s);i++{ for j:=0;j<len(p);j++{     ii,jj:=i+1,j+1     if s[i]==p[j] || p[j]=='?'{  dp[ii][jj]=dp[i][j]     }else if p[j]=='*'{  dp[ii][jj]=dp[i][jj] || dp[ii][j]     }else {  dp[ii][jj]=false     } }    }    return dp[len(s)][len(p)]}