func IsMatch(s string, p string) bool {
	memo := make([][]bool, len(s))
	visited := make([][]bool, len(s))
	for i := range memo {
		memo[i] = make([]bool, len(p))
		visited[i] = make([]bool, len(p))
	}

	return isMatchHelper(s, 0, p, 0, memo, visited)
}

func isMatchHelper(s string, sIndex int, p string, pIndex int, memo [][]bool, visited [][]bool) bool {
	// 如果 p 从pIdex开始是空字符串了，那么 s 也必须从 sIndex 是空才能匹配上
	if pIndex == len(p) {
		return sIndex == len(s)
	}

	// 如果 s 从 sIndex 是空，那么p 必须全是 *
	if sIndex == len(s) {
		return allStar(p, pIndex)
	}

	if visited[sIndex][pIndex] {
		return memo[sIndex][pIndex]
	}

	sChar := s[sIndex]
	pChar := p[pIndex]
	match := false

	if pChar == '*' {
		match = isMatchHelper(s, sIndex, p, pIndex+1, memo, visited) ||
			isMatchHelper(s, sIndex+1, p, pIndex, memo, visited)
	} else {
		match = charMatch(sChar, pChar) &&
			isMatchHelper(s, sIndex+1, p, pIndex+1, memo, visited)
	}

	visited[sIndex][pIndex] = true
	memo[sIndex][pIndex] = match
	return match
}

func charMatch(sChar, pChar byte) bool {
	return sChar == pChar || pChar == '?'
}

func allStar(p string, pIndex int) bool {
	for i := pIndex; i < len(p); i++ {
		if p[i] != '*' {
			return false
		}
	}
	return true
}

func IsMatchRE(s string, p string) bool {
	memo := make([][]bool, len(s))    // 记忆搜索结果
	visited := make([][]bool, len(s)) // 标记是否访问
	for i := range memo {
		memo[i] = make([]bool, len(p))
		visited[i] = make([]bool, len(p))
	}

	return isMatchHelperRE(s, 0, p, 0, memo, visited)
}

func isMatchHelperRE(s string, sIndex int, p string, pIndex int, memo [][]bool, visited [][]bool) bool {
	// "" == ""
	if pIndex == len(p) { // 如果p已经匹配完毕
		return sIndex == len(s) // 根据s是否匹配完毕即可
	}

	if sIndex == len(s) { // 如果s匹配完毕
		return isEmpty(p, pIndex)
	}

	if visited[sIndex][pIndex] {
		return memo[sIndex][pIndex]
	}

	sChar := s[sIndex]
	pChar := p[pIndex]
	match := false

	// Consider a* as a bundle
	if pIndex+1 < len(p) && p[pIndex+1] == '*' { // 如果为'*'，有两种方案
		match = isMatchHelperRE(s, sIndex, p, pIndex+2, memo, visited) || // '*'不去匹配字符
			charMatchRE(sChar, pChar) && isMatchHelperRE(s, sIndex+1, p, pIndex, memo, visited) // '*'重复前面一个字符去匹配s
	} else {
		match = charMatchRE(sChar, pChar) && // 如果当前两字符匹配
			isMatchHelperRE(s, sIndex+1, p, pIndex+1, memo, visited) // 继续下一个字符匹配
	}

	visited[sIndex][pIndex] = true // 搜索完成就标记
	memo[sIndex][pIndex] = match   // 存储搜索结果
	return match
}

func charMatchRE(sChar, pChar byte) bool { // 判断两字符是否匹配
	return sChar == pChar || pChar == '.'
}

func isEmpty(p string, pIndex int) bool { // 形如"x*x*"形式
	for i := pIndex; i < len(p); i += 2 {
		if i+1 >= len(p) || p[i+1] != '*' { // 如果不是'*'，无法匹配
			return false
		}
	}
	return true
}

func WordPatternMatch(pattern string, str string) bool {
	return isMatch(pattern, str, map[rune]string{}, map[string]struct{}{})
}

func isMatch(pattern string, str string, mapping map[rune]string, used map[string]struct{}) bool {
	if len(pattern) == 0 {
		return len(str) == 0
	}

	char := rune(pattern[0])
	if word, ok := mapping[char]; ok {
		if !strings.HasPrefix(str, word) {
			return false
		}
		return isMatch(pattern[1:], str[len(word):], mapping, used)
	}

	for i := 0; i < len(str); i++ {
		word := str[:i+1]
		if _, exists := used[word]; exists {
			continue
		}

		used[word] = struct{}{}
		mapping[char] = word

		if isMatch(pattern[1:], str[i+1:], mapping, used) {
			return true
		}

		delete(mapping, char)
		delete(used, word)
	}

	return false
}

func WordBreak(s string, wordSet map[string]struct{}) bool {
	if s == "" {
		return true
	}

	n := len(s)
	dp := make([]bool, n+1)
	dp[0] = true

	maxLength := 0
	for word := range wordSet {
		if len(word) > maxLength {
			maxLength = len(word)
		}
	}

	for i := 1; i <= n; i++ {
		for l := 1; l <= maxLength; l++ {
			if i < l {
				break
			}
			if !dp[i-l] {
				continue
			}
			word := s[i-l : i]
			if _, ok := wordSet[word]; ok {
				dp[i] = true
				break
			}
		}
	}

	return dp[n]
}

func WordBreak 3 (s string, dict map[string]struct{}) int {
	n := len (s)
	lowerS := strings.ToLower (s)

	lowerDict := make (map[string]struct{})
	for str := range dict {
		lowerDict[strings.ToLower (str)] = struct{}{}
	}

	dp := make ([][]int, n)
	for i := range dp {
		dp[i] = make ([]int, n)
	}

	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			sub := lowerS[i : j+1]
			if _, exists := lowerDict[sub]; exists {
				dp[i][j] = 1
			}
		}
	}

	for i := 0; i < n; i++ {
		for j := i; j < n; j++ {
			for k := i; k < j; k++ {
				dp[i][j] += dp[i][k] * dp[k+1][j]
			}
		}
	}

	return dp[0][n-1]
}