package main

// ? any character; * any chatacter with any length
func isMatch(s string, p string) (ans bool) {
	m, n := len(s), len(p)
	match := make([][]bool, m+1)
	for i := range match {
		match[i] = make([]bool, n+1)
	}
	match[0][0] = true
	for i := 1; i <= n; i++ {
		if p[i-1] == '*' {
			match[0][i] = true
		} else {
			break
		}
	}
	for y := 1; y <= m; y++ {
		for x := 1; x <= n; x++ {
			if s[y-1] == p[x-1] || p[x-1] == '?' {
				match[y][x] = match[y-1][x-1]
			} else if p[x-1] == '*' {
				// Star matches empty string or matches next character
				match[y][x] = match[y][x-1] || match[y-1][x]
			}
		}
	}
	return match[m][n]
}

// func main() {
// 	println(isMatch("", ""))
// 	println(isMatch("", "**"))
// 	println(isMatch("aa", "a?"))
// 	println(isMatch("aaa", "*"))
// 	println(isMatch("cab", "c*b"))
// 	println(isMatch("abc", "*c*a"))
// }