题解 | 字符串通配符

/* 
    动态规划
 */
package main

import (
	"fmt"
	"strings"
)

// 判断字符是否为数字或字母
func isNumOrChar(b byte) bool {
	return (b >= '0' && b <= '9') ||
		(b >= 'a' && b <= 'z') ||
		(b >= 'A' && b <= 'Z')
}

// 不区分大小写的字符比较
func equalIgnoreCase(a, b byte) bool {
	return strings.ToLower(string(a)) == strings.ToLower(string(b))
}

// 检查通配符 s 是否匹配目标字符串 p
func check(s, p string) bool {
	m, n := len(s), len(p)
	
	// dp[i][j] 表示 s[:i] 是否匹配 p[:j]
	dp := make([][]bool, m+1)
	for i := range dp {
		dp[i] = make([]bool, n+1)
	}
	
	// 空模式匹配空字符串
	dp[0][0] = true
	
	// 处理 s 开头的 '*' 可以匹配空字符串
	for i := 1; i <= m; i++ {
		if s[i-1] == '*' {
			dp[i][0] = dp[i-1][0]
		} else {
			break // '*' 连续才有意义
		}
	}
	
	// 填充 DP 表
	for i := 1; i <= m; i++ {
		for j := 0; j <= n; j++ {
			if s[i-1] == '*' {
				// '*' 匹配 0 个：dp[i-1][j]
				// '*' 匹配多个：dp[i][j-1]（如果 j>0）
				dp[i][j] = dp[i-1][j]
				if j > 0 {
					dp[i][j] = dp[i][j] || dp[i][j-1]
				}
			} else if s[i-1] == '?' {
				// '?' 必须匹配一个数字或字母
				if j > 0 && isNumOrChar(p[j-1]) {
					dp[i][j] = dp[i-1][j-1]
				}
			} else {
				// 普通字符
				if j > 0 {
					if isNumOrChar(s[i-1]) {
						// 字母：不区分大小写匹配
						dp[i][j] = dp[i-1][j-1] && equalIgnoreCase(s[i-1], p[j-1])
					} else {
						// 其他字符：精确匹配
						dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1])
					}
				}
			}
		}
	}
	
	return dp[m][n]
}

func main() {
	var s, p string
	fmt.Scanf("%s", &s)
	fmt.Scanf("%s", &p)
	
	// 注意：我们不提前转小写，因为在 equalIgnoreCase 中处理
	result := check(s, p)
	if result {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}