程序员代码面试指南：字符串匹配问题

题目链接：https://www.nowcoder.com/practice/7ab95c2bbfc941a89c13c78128914e14?tpId=101&tqId=33204&tPage=7&rp=7&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking
题目描述
对于字符串str，其中绝对不含有字符’.’和‘’。再给定字符串exp，其中可以含有’.’或’‘’，’’字符不能是exp的首字符，并且任意两个’‘字符不相邻。exp中的’.’代表任何一个字符，exp中的’’表示’‘的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配(注意：输入的数据不保证合法，但只含小写字母和‘.’和‘*’)。
输入包含两行，两个字符串，分别代表str和exp(str和len长度大于等于1小于等于300）
如果str是能被exp匹配，请输出“YES”，否则输出“NO”。

采用动态规划的思路，dp[i][j]表示str[i]到str最后一个字符和exp[j]到exp最后一个字符是否匹配。
我们分三种情况讨论：
1、exp[j]是字母。如果exp[j+1]不是*号，则exp[j]必须匹配str[i]的第一个字符，接下来就判断str[i+1]到最后和exp[j+1]到最后是否匹配，所以：

dp[i][j]=(str[i]==exp[j] && dp[i+1][j+1])

如果exp[j+1]是星号的话，那么exp[j]可以有0个或多个，如果exp[j]有0个，等价于str[i]到最后和exp[j+2]到最后是否匹配，如果exp[j]有多个，则首先匹配exp[j]和str[i]，由于exp[j]可以有多个，所以之后可能还会有exp[j]和str[i]的字符匹配，此时等价于str[i+1]到最后和exp[j]是否匹配，所以当exp[j+1]是星号的话，可以得到：

dp[i][j]=dp[i][j+2] || (str[i]==exp[j] && dp[i+1][j])

2、exp[j]是字符'.'的时候，与情况1类似，由于'.'可以匹配任意字符，所以求解dp的时候删去str[i]==exp[j]的判断就可以。

3、exp[j]是星号'*'，此时exp[j]前面的字符可以有一个或多个，分情况讨论即可：首先如果有0个exp[j+1]判断str[i]到最后和exp[j+1]到最后是否匹配。
接着设定变量k，初始k=i，如果str[k]==exp[j-1]，此时表示有一个exp[j-1]，此时判断str[k+1]到最后和exp[j+1]到最后是否匹配，如果不匹配：
k=i+1,如果str[k]==exp[j-1]，此时表示有两个exp[j-1]，再判断str[k+1]到最后和exp[j+1]到最后是否匹配，如果不匹配，k=i+2，以此类推，如果在这个过程中，str[k+1]和exp[j+1]匹配了，则dp[i][j]=true，如果遍历到str[k]!=exp[j-1]或者k到了str最后，则dp[i][j]=false。

最后处理一下边界条件，我是这么处理的：设length(str)=n,length(exp)=m,则dp[n][m]=true,dp[i][m]=false(0<=i<n)。

如果exp[j]==''，则dp[n][j]=dp[n][j+1]。
如果exp[j]!=''且exp[j+1]=='*',则dp[n][j]=dp[n][j+2]
否则,dp[n][j]=false

package main
import(
    "fmt"
)
var str,exp string
func main(){
    fmt.Scan(&str)
    fmt.Scan(&exp)
    solve()
}
func solve(){
    n,m:=len(str),len(exp)
    for _,v:=range str{
        if !(v>='a' && v<='z'){
            fmt.Println("NO")
            return
        }
    }
    for i,v:=range exp{
        if i==0 && exp[i]=='*'{
            fmt.Println("NO")
            return
        }
        if exp[i]=='*' && i+1<m && exp[i+1]=='*'{
            fmt.Println("NO")
            return
        }
        if !((v>='a' && v<='z') || (v=='.') || (v=='*')){
            fmt.Println("NO")
            return
        }
    }
    dp:=make([][]bool,n+1)
    for i:=0;i<=n;i++{
        dp[i]=make([]bool,m+1)
    }
    for i:=0;i<=n;i++{
        for j:=0;j<=m;j++{
            dp[i][j]=false
        }
    }
    for i:=n;i>=0;i--{
        for j:=m;j>=0;j--{
            if j==m{
                dp[i][j]=(i==n)
            }else if i==n{
                if exp[j]=='*'{
                    dp[i][j]=dp[i][j+1]
                }else if j+1<m && exp[j+1]=='*'{
                    dp[i][j]=dp[i][j+2]
                }
            }else if exp[j]=='.'{
                if j+1<m && exp[j+1]=='*'{
                    dp[i][j]=(dp[i][j+2]) || (dp[i+1][j])
                }else{
                    dp[i][j]=dp[i+1][j+1]
                }
            }else if exp[j]=='*'{
                //*之前0个字符
                if dp[i][j+1]{
                    dp[i][j]=true
                    continue
                }
                //*之前多于0个字符
                for k:=i;k<n;k++{
                    if exp[j-1]!='.' && str[k]!=exp[j-1]{
                        break
                    }else if dp[k+1][j+1]{
                        dp[i][j]=true
                        break
                    }
                }
            }else{
                if j+1<m && exp[j+1]=='*'{
                    dp[i][j]=(dp[i][j+2]) || (str[i]==exp[j] && dp[i+1][j])
                }else{
                    dp[i][j]=(str[i]==exp[j] && dp[i+1][j+1])
                }
            }
        }
    }
    if dp[0][0]{
        fmt.Println("YES")
    }else{
        fmt.Println("NO")
    }
}