0044.通配符匹配

https://leetcode.cn/problems/wildcard-matching/

方法一：回溯 + 记忆化搜索

暴力搜索，不过可以通过数组进行优化，时间复杂度 $O(m^n)$，空间复杂度 $O(m \times n)$。

func isMatch(s string, p string) bool {
	// 1表示匹配， 2表示不匹配
	memo, m, n := make([][]int, len(s)+10), len(s), len(p)
	for i := 0; i < m+10; i++ {
		memo[i] = make([]int, n+10)
	}
	var backtrack func(p1, p2 int) bool

	backtrack = func(p1, p2 int) bool {
		if memo[p1][p2] != 0 {
			return memo[p1][p2] == 1
		}
		if p2 >= n {
			if p1 >= m {
				memo[p1][p2] = 1
			} else {
				memo[p1][p2] = 2
			}
			return memo[p1][p2] == 1
		}
		ans := false
		if p1 <= m && p[p2] == '*' {
			ans = backtrack(p1, p2+1) || backtrack(p1+1, p2)
		}

		if p1 < m && p[p2] == '?' {
			ans = backtrack(p1+1, p2+1)
		} else if p1 < m && s[p1] == p[p2] {
			ans = backtrack(p1+1, p2+1)
		}
		memo[p1][p2] = 2
		if ans {
			memo[p1][p2] = 1
		}
		return ans
	}
	return backtrack(0, 0)
}

方法二：动态规划

时间复杂度 $O(m \times n)$，空间复杂度 $O(m \times n)$。

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