LC139 - 单词拆分

package DP

import "strings"

func wordBreak(s string, wordDict []string) bool {
    size := len(s)
    dp := make([]int, size)
    for i := 0; i < len(dp); i++ {
        dp[i] = -1
    }
    var f func(int) bool
    f = func(index int) bool {
        if index == size {
            return true
        }
        if dp[index] != -1 {
            return dp[index] == 1
        }
        ret := false
        for _, word := range wordDict {
            ret = ret || startsWith(s, word, index) && f(index+len(word))
        }
        if ret {
            dp[index] = 1
        } else {
            dp[index] = 0
        }
        return ret
    }
    return f(0)
}

func startsWith(s, word string, index int) bool {
    curStr := s[index:]
    return strings.HasPrefix(curStr, word)
}