题解 | 字符串的交错组成

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		str1 := scanner.Text()
		if len(str1) == 0 {
			break
		}
		scanner.Scan()
		str2 := scanner.Text()
		scanner.Scan()
		aim := scanner.Text()

		if process3(str1, str2, aim) {
			fmt.Println("YES")
		} else {
			fmt.Println("NO")
		}
	}
}

// func process(str1, str2, aim string) bool {
// 	return subprocess(0, 0, str1, str2, aim)
// }

// func subprocess(i, j int, str1, str2, aim string) bool {
// 	if len(str1)+len(str2) != len(aim) {
// 		return false
// 	}
// 	if i+j == len(aim) {
// 		return true
// 	}

// 	find1 := false
// 	if i < len(str1) && str1[i] == aim[i+j] {
// 		find1 = subprocess(i+1, j, str1, str2, aim)
// 	}
// 	find2 := false
// 	if j < len(str2) && str2[j] == aim[i+j] {
// 		find2 = subprocess(i, j+1, str1, str2, aim)
// 	}
// 	return find1 || find2
// }

func process2(str1, str2, aim string) bool {
	if len(str1)+len(str2) != len(aim) {
		return false
	}
	dp := make([][]bool, len(str1)+1)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]bool, len(str2)+1)
	}
	dp[len(str1)][len(str2)] = true

	for j := len(str2) - 1; j >= 0; j-- {
		if str2[j] == aim[j+len(str1)] {
			dp[len(str1)][j] = dp[len(str1)][j+1]
		}
	}

	for i := len(str1) - 1; i >= 0; i-- {
		if str1[i] == aim[i+len(str2)] {
			dp[i][len(str2)] = dp[i+1][len(str2)]
		}
	}

	for i := len(str1) - 1; i >= 0; i-- {
		for j := len(str2) - 1; j >= 0; j-- {
			find1 := false
			if str1[i] == aim[i+j] {
				find1 = dp[i+1][j]
			}
			find2 := false
			if str2[j] == aim[i+j] {
				find2 = dp[i][j+1]
			}
			dp[i][j] = find1 || find2
		}
	}
	return dp[0][0]
}

func process3(str1, str2, aim string) bool {
	if len(str1)+len(str2) != len(aim) {
		return false
	}
  
    // 原有逻辑上改进空间
	dp := make([]bool, len(str2)+1)
	dp[len(str2)] = true

	for j := len(str2) - 1; j >= 0; j-- {
		if str2[j] == aim[j+len(str1)] {
			dp[j] = dp[j+1]
		}
	}

	for i := len(str1) - 1; i >= 0; i-- {
		for j := len(str2); j >= 0; j-- {
			if j == len(str2) {
				if str1[i] != aim[i+len(str2)] {
					dp[j] = false
				}
			} else {
				find1 := false
				if str1[i] == aim[i+j] {
					find1 = dp[j]
				}
				find2 := false
				if str2[j] == aim[i+j] {
					find2 = dp[j+1]
				}
				dp[j] = find1 || find2
			}
		}
	}

	return dp[0]
}