版权声明:原创勿转 https://cloud.tencent.com/developer/article/1412853
dp算法
dpi表示字符串s:i是否符合要求。如果sj:i在给定的字符串组中,且dpj为true(即字符串s:j能够拆分成符合要求的子字符串),那么此时dpi也为true
func wordBreak(s string, wordDict []string) bool {
l := len(s)
flags := make([]bool, l+1)
flags[0] = true
for i := 1; i <= l; i++ {
for j := 0; j < i; j++ {
if flags[j] == true && contain(s[j:i], wordDict) {
flags[i] = true
break
}
}
}
return flags[l]
}
func contain(s string, wordDict []string) bool {
for _, v := range wordDict {
if s == v {
return true
}
}
return false
}