单词拆分
题目链接: https://leetcode.cn/problems/word-break/
解题思路:
若s可以利用字典拼出,则s去掉某个字典内的单词剩下的也可以用字典内出现的单词拼出
可以利用哈希表存储字典单词
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]
}
复杂度分析
时间复杂度: 时间复杂度是
空间复杂度: 空间复杂度是
最后更新于
这有帮助吗?