单词拆分

题目链接: https://leetcode.cn/problems/word-break/

解题思路：

1. 若s可以利用字典拼出，则s去掉某个字典内的单词剩下的也可以用字典内出现的单词拼出

2. 可以利用哈希表存储字典单词

3. dp[i]=dp[j]&&dict(s[j:i])

func wordBreak(s string, wordDict []string) bool {
    wordDictMap := make(map[string]bool)
    for _,v := range wordDict {
        wordDictMap[v]=true
    }
    n := len(s)
    dp := make([]bool,n+1)
    dp[0]=true
    for i := 1;i<=n;i++{
        for j:=0;j<i;j++{
            if dp[j] && wordDictMap[s[j:i]]{
                dp[i]=true
                break
            }
        }
    }
    return dp[n]
}

复杂度分析

• 时间复杂度： 时间复杂度是 $O(n²)$
• 空间复杂度： 空间复杂度是 $O(n)$