题解 | #正则表达式匹配#

package main

import (
	"fmt"
)

func main() {
	var str, pattern string
	fmt.Scan(&str, &pattern)
	m := len(str)
	n := len(pattern)
	var dp = make([][]bool, m+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]bool, n+1)
	}
	// for i := 0; i <= n; i++ {
	// 	dp[0][i] = true
	// }
	dp[0][0] = true

	for i := 0; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if i >0 && (pattern[j-1] == str[i-1] || pattern[j-1] == '.') {
				dp[i][j] = dp[i-1][j-1]
			} else if pattern[j-1] == '*' {
				dp[i][j] = dp[i][j-2]

				if i >0 &&(pattern[j-2] == str[i-1] || pattern[j-2] == '.') {
					dp[i][j] = dp[i-1][j] || dp[i][j]
				}
			}
		}
	}
	fmt.Println(dp[m][n])
	// for  i:=0; i<=n; i++ {
	// 	if dp[m][i] == true {
	// 		fmt.Println(true)
	// 		return
	// 	}
	// }
	// fmt.Println(false)
}