单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
思路
动态规划,使用一个dp数组存储以字符串s中每个元素i为结尾的子串s[:i+1]是否可以由字典中出现的单词拼接出。而对于某个元素s[j],以它结尾的子串s[:j+1]可不可以由字典中出现的单词拼接得到取决于:
- s[:j+1]是否出现在字典中
- 找到j之前的使得dp[i] == 1的i(即s[:i+1]可以由字典中出现的单词拼接得到),如果s[i+1,j+1]这个子串在字典中,则以s[j]为结尾的子串s[:j+1]可以由字典中的单词拼接得到
这两种情况满足其一即可确定满足条件
代码
代码
func wordBreak(s string, wordDict []string) bool {
mapW := make(map[int]int)
for i := 0; i<len(s); i++ {
mapW[i] = 0
}
mapK := make(map[string]int)
for i := 0; i<len(wordDict); i++ {
mapK[wordDict[i]] = 1
}
for i := 0;i<len(s); i++ {
str := s[:i+1]
if mapK[str] == 1 {
mapW[i] = 1
}else{
for j := 0;j< i;j++ {
if mapW[j] == 1 {
str1 := s[j+1:i+1]
if mapK[str1] == 1 {
mapW[i] = 1
break
}
}
}
}
}
if mapW[len(s)-1] == 1 {
return true
}else{
return false
}
}
性能
执行用时:0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗:2.2 MB, 在所有 Go 提交中击败了11.86%的用户
通过测试用例:45 / 45
空间复杂度表现差一部分因为dp数组写成了map,改成数组应该会改善一些。
碎碎念:泪目,第一次medium思路代码一把AC且性能完美。