139. 单词拆分

139.go

// s = "catsandog"
// wordDict = ["cats", "dog", "sand", "and", "cat"]
// dp[0] = "" => true
// dp[1] = "c" => false
// dp[2] = "ca" => false
// dp[3] = "cat" -> dp[0] && wordMap["cat"] => true
// dp[4] = "cats" -> dp[0] && wordMap["cats"] => true
// dp[5] = "catsa" => false
// dp[6] = "catsan" => false
// dp[7] = "catsand" -> dp[3] && wordMap["sand"] => true
// dp[8] = ... => false
// dp[9] = "catsandog" => false
func wordBreak(s string, wordDict []string) bool {
    wordMap := make(map[string]bool, len(wordDict))
    for _, word := range(wordDict) {
        wordMap[word] = true
    }
    
    dp := make([]bool, len(s) + 1)
    dp[0] = true
    
    trueIndex := make([]int, 0)
    trueIndex = append(trueIndex, 0)
    
    for i := 1; i <= len(s); i++ {
        for _, j := range(trueIndex) {
            if dp[j] && wordMap[s[j:i]] {
                dp[i] = true
                trueIndex = append(trueIndex, i)
                break
            }
        }
    }
    return dp[len(s)]
}