139. 单词拆分(Medium)

Go 示例

深度搜索

// 超时 36 / 43 
func dfs(s string) bool {
    if len(s) == 0 {
        return true 
    }
    for i := 0; i < len(s); i++ {
        _, ok := wordMap[s[:i + 1]]
        if ok {
            if dfs(s[i + 1:]) {
                return true 
            }
        }
    }
    return false 
}

var wordMap map[string] bool 

func wordBreak(s string, wordDict []string) bool {
    if len(s) == 0 {
        return true 
    }
    wordMap = make(map[string] bool )

    for _, v := range wordDict {
        wordMap[v] = true 
    }
    
    return dfs(s)
}

动态规划

func contains(wordMap map[string] bool, s string) bool {
    _, ok := wordMap[s]
    return ok
}

func wordBreak(s string, wordDict []string) bool {
    dp := make([]bool, len(s) + 1)
    wordMap := make(map[string] bool)
    for _, v := range wordDict {
        wordMap[v] = true
    }
    
    dp[0] = true
    for i:= 1; i <= len(s); i++ { // 前 i 个
        for j:= 0; j < i ; j++ { // 从 j 开始
            if dp[j] && contains(wordMap, s[j : i]){
               dp[i] = true
            }
        }
    }
    return dp[len(s)]
}

剪枝：可以做进一步优化，当截取的长度超过字典的最大单词长度的时候，一定匹配不到。

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func maxLength(wordDict []string) (int, map[string]bool ) {
    maxWordLength := 0
    wordMap := make(map[string]bool)
    for _, v := range wordDict {
        wordMap[v] = true
        maxWordLength = max(len(v), maxWordLength)
    }
    return maxWordLength, wordMap
}

func contains(wordMap map[string]bool, s string) bool {
    _, ok := wordMap[s]
    return ok
}

func wordBreak(s string, wordDict []string) bool {
    if len(s) == 0 {
        return false
    }

    dp := make([]bool, len(s) + 1)
    dp[0] = true
    maxWordLength, wordMap := maxLength(wordDict) // 单词最大长度
    for i := 1; i <= len(s); i++ {
        for j:=0; j < i; j++ {
            // 1. 前 j 个字母成功分割 2. 小于单词最大长度 3. 字典找到
            if dp[j] && i - j <= maxWordLength && contains(wordMap, s[j: i]) {
                dp[i] = true 
                break // 前 i 个字母被成功分割
            }
        }
    }
    return dp[len(s)]
}