【每日一题】- 2020-10-21 - 字典分割

[azl397985856]

这是微软 4 面的编程题。

题目描述

将给定的字符串进行分割， 分割的依据是使得分割后的单词全部在字典 dict 中，如果分割后不在 dict 中， 则返回空。

eg:

const dict = {
 hi: true
 hello: true,
 world: true
};

const str = spaceSeparator('helloworld'); // "hello world"
const str2 = spaceSeparator('helloworldhi'); // "hello world hi"
const str2 = spaceSeparator('helloworldh'); // "" , as h is not present in dict we throw "" as output

力扣类似题目

• 140. 单词拆分 II

扩展

完整的微软面经，参考 https://dev.to/dhilipkmr/software-engineer-2-ui-interview-at-microsoft-1i0b

[azl397985856]

由于题目和 140. 单词拆分 II 一样， 因此我就以力扣的这道题讲好了。

暴力回溯

思路

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

代码

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)$。

代码

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

        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，这个留给大家来完成。

我整理的 1000 多页的电子书已经开发下载了，大家可以去我的公众号《力扣加加》后台回复电子书获取。

[stale[bot]]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.