单词拆分

1. 题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

2. 思路

• 说白了就是从字典中任取N个，如果能匹配s，那么就是true
• DFS
• DFS+记忆化

3. 实现

3.1. DFS

//DFS
func wordBreak(s string, wordDict []string) bool {
    m := make(map[string]bool, 0)
    for _, word := range wordDict {
        m[word] = true
    }
    return wordBreakDFS(s, 0, m)
}

func wordBreakDFS(s string, index int, m map[string]bool) bool {
    if index == len(s) {
        return true
    }
    for i := index+1; i <= len(s); i++ {
        current := s[index:i]
        if m[current] && wordBreakDFS(s, i, m) {
            return true
        }
    }
    return false
}

3.2. DFS+记忆化

func wordBreak(s string, wordDict []string) bool {
    m := make(map[string]bool, 0)
    for _, word := range wordDict {
        m[word] = true
    }
    memo := make(map[int]bool, 0)
    return wordBreakDFS(s, 0, m, memo)
}

func wordBreakDFS(s string, index int, m map[string]bool, memo map[int]bool) bool {
    if index == len(s) {
        return true
    }
    canBreak, ok := memo[index]
    if ok {
        return canBreak
    }
    canBreak = false
    for i := index+1; i <= len(s); i++ {
        current := s[index:i]
        if m[current] && wordBreakDFS(s, i, m, memo) {//注意这里需要枚举所有结果，所以不能直接return wordBreakDFS
            canBreak =  true
        }
    }
    memo[index] = canBreak
    return canBreak
}

4. 参考

• 139. 单词拆分 - 力扣（LeetCode）