Leetcode 单词拆分

2023-04-29

单词拆分

给你一个字符串 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且性能完美。

评论