代码随想录训练营 dp

背包问题结束了，我也要准备转正了

139. 🌸单词拆分🌸

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

func wordBreak(s string, wordDict []string) bool {
    wordSet :=make(map[string]bool)

    for _,w:=range wordDict{
        wordSet[w] =true
    }

    dp:=make([]bool,len(s)+1)
    dp[0] = true
    for i:=1;i<=len(s);i++{//package
        for j:=0;j<i;j++{
            if dp[j] && wordSet[s[j:i]]{
                dp[i] =true
                break
            }
        }
    }
    return dp[len(s)]
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20