1. 首页
  2. LeetCode 刷题网

LeetCode 140. 单词拆分 II

题目描述

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。

说明:

分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:

输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
  "cats and dog",
  "cat sand dog"
]
示例 2:

输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3:

输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]

微软有一道题和这个一样 题目地址 一样,感兴趣的可以看看完整面经。

难度:Middle

前置知识

  • 回溯
  • 笛卡尔积

公司

  • 暂无

暴力回溯

思路

实际上这道题就是暴力回溯就好了, 代码也比较简单。

代码

代码支持:Python3

Python3 Code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        ans = []
        n = len(s)

        def backtrack(temp, start):
            if start == n: ans.append(temp[1:])
            for i in range(start, n):
                if s[start:i + 1] in wordDict:
                    backtrack(temp + " " + s[start:i + 1], i + 1)
        backtrack('', 0)
        return ans

复杂度分析

  • 时间复杂度:$O(2^N)$
  • 空间复杂度:$O(2^N)$

笛卡尔积优化

思路

上面的代码会超时,测试用例会挂在如下:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"[
  ("a",
  "aa",
  "aaa",
  "aaaa",
  "aaaaa",
  "aaaaaa",
  "aaaaaaa",
  "aaaaaaaa",
  "aaaaaaaaa",
  "aaaaaaaaaa")
];

也就是说 s 的长度是 151, 这超时也就能够理解了,但是力扣的题目描述没有给数据范围。 如果是真实的面试, 一定先问清楚数据范围

接下来,我们考虑优化。

通过观察发现, 对于一个字符串 s,比如 “helloworldhi” 而言,假设 dict 为:

{
  hi: true,
  h: true,
  i: true,
  world: true,
  hello: true,

}
  1. 当我们 DFS 探到底部的时候,也就是触及到 hi。我们就知道了,s[-2:] 可能组成的所有可能就是 [‘hi’, ‘h’, ‘i’]
  2. 当我们 DFS 探到 worldhi 的时候。我们就知道了,s[-7:] 可能组成的所有可能就是 [‘worldhi’, ‘worldh’, ‘worldi’]
  3. 如上只是一个分支的情况,如果有多个分支,那么步骤 1 就会被重复计算。

我们也不难看出, 当我们 DFS 探到 worldhi 的时候,其可能的结果就是探测到的单词和上一步的所有可能的笛卡尔积。

因此一种优化思路就是将回溯的结果通过返回值的形式传递给父级函数,父级函数通过笛卡尔积构造 ans 即可。而这实际上和上面的解法复杂度是一样的, 但是经过这样的改造,我们就可以使用记忆化技巧减少重复计算了。因此理论上, 我们不存在回溯过程了。 因此时间复杂度就是所有的组合,即一次遍历以及内部的笛卡尔积,也就是 $O(N ^ 2)$。

代码

代码支持:Python3

Python3 Code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        @lru_cache(None)
        def backtrack(start):
            ans = []
            if start == n:
                ans.append('')
            for i in range(start, n):
                if s[start:i + 1] in wordDict:
                    if start == 0: temp = s[start:i + 1]
                    else: temp = " " + s[start:i + 1]
                    ps = backtrack(i + 1)
                    for p in ps:
                        ans.append(temp + p)
            return ans
        return backtrack(0)

复杂度分析

  • 时间复杂度:$O(N^2)$
  • 空间复杂度:$O(N^2)$

这种记忆化递归的方式和 DP 思想一模一样, 大家可以将其改造为 DP,这个留给大家来完成。

更多题解可以访问我的 JS中文网 – 码农周刊 仓库:https://github.com/meibin08/free-programming-books, 一起学习更多前端前沿知识。

看完两件小事

如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:

  1. 关注我们的 GitHub 博客,让我们成为长期关系
  2. 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
  3. 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程

JS中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。欢迎热爱技术的你一起加入交流与学习,JS中文网的使命是帮助开发者用代码改变世界

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com

标题:LeetCode 140. 单词拆分 II

链接:https://www.javascriptc.com/4504.html

« React Error Boundaries
LeetCode 139. 单词拆分»
Flutter 中文教程资源

相关推荐

QR code