139.M 单词拆分

Problem: 139. 单词拆分

思路

动态规划。

用dp[i]表示前i个字符是否可以被拼出，则有：

dp[i] = dp[j] && check(s[j:i])

对于边界条件，我们定义dp[0]=true表示空串且合法。

Code

func wordBreak(s string, wordDict []string) bool {
	m := make(map[string]bool)
	for _, word := range wordDict {
		m[word] = true
	}

	dp := make([]bool, len(s)+1)
	dp[0] = true //空字符串可以被拆分
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			// 划分为[0:j]和[j:i]这两段
			if dp[j] && m[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}

	return dp[len(s)]
}