139.单词拆分
139.单词拆分
题解
//state: dp[i]表示s[0,i)的串是否合法
//function: dp[i] = dp[j] && check[j,i)
//intialize:dp[0] = true
//answer: dp[len(s)] = true
代码
package main func wordBreak(s string, wordDict []string) bool { dp := make([]bool, len(s)) dp[0] = true wordmap := make(map[string]bool) for _, v := range wordDict { wordmap[v] = true } for i := 1; i <= len(s); i++ { for j := 0; j < i; j++ { if dp[j] && wordmap[s[j+1:i]] { dp[i] = true } } } return dp[len(s)] }
