139. Word Break

// 序列 DP, dp[i]: s[0:i]能否被组成
// 时间O(n^2), 空间O(n)
func wordBreak(s string, wordDict []string) bool {
    n := len(s)
    wordDictSet := make(map[string]bool)
    for _, v := range wordDict {
        wordDictSet[v] = true
    }
    dp := make([]bool, n + 1)
    dp[0] = true
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            if dp[j] && wordDictSet[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }
    return dp[n];
}