Skip to content

Latest commit

 

History

History
173 lines (124 loc) · 5.12 KB

139.word-break.md

File metadata and controls

173 lines (124 loc) · 5.12 KB

题目地址(139. 单词拆分)

https://leetcode-cn.com/problems/word-break/

题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

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

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。
示例 3:

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

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这道题是给定一个字典和一个句子,判断该句子是否可以由字典里面的单词组出来,一个单词可以用多次。

暴力的方法是无解的,复杂度比较高,但是可以通过。

暴力思路是从匹配位置 0 开始匹配, 在 wordDict 中一个个找,如果其能和 s 匹配上就尝试进行匹配,并更新匹配位置。

比如 s = "leetcode", wordDict = ["leet", "code"]。

那么:

  • 先试试 leet 可以匹配么?可以的,匹配后 s 剩下 code,继续在 wordDict 中找。
  • leet 可以匹配么?不能!code 能够匹配么?可以!返回 true 结束

如果 wordDict 遍历一次没有任何进展,那么直接返回 false。

注意到如果匹配成功一次后,本质是把问题规模缩小了,问题性质不变,因此可以使用动态规划来解决。

@cache
def dp(pos):
    if pos == len(s): return True
    for word in wordDict:
        if s[pos:pos+len(word)] == word and dp(pos + len(word)): return True
    return False
return dp(0)

复杂度为 $O(n^2 * m)$ 其中 n 为 s 长度, m 为 wordDict 长度。

我们用图来感受一下:

139.word-break-1

接下来我们以题目给的例子分步骤解读一下:

(以下的图左边都代表 s,右边都是 dict,灰色代表没有处理的字符,绿色代表匹配成功,红色代表匹配失败)

139.word-break-2

139.word-break-3

139.word-break-4

139.word-break-5

上面分步解释了算法的基本过程,下面我们感性认识下这道题,我把它比喻为 你正在往一个老式手电筒🔦中装电池

139.word-break-6

我们可以进一步优化, 使得复杂度和 m 无关。优化的关键是在 dp 函数内部枚举匹配的长度 k。这样我们截取 s[pos:pos+k] 其中 pos 表示当前匹配到的位置。然后只要看 s[pos:pos+k] 在 wordDict 存在与否就行。存在了就更新匹配位置继续,不存在就继续。而看 s[pos:pos+k] 在 wordDict 存在与否就行 是可以通过将 wordDict 中放入哈希集合中进行优化的,时间复杂度 O(1),牺牲一点空间,空间复杂度 O(m)

代码

代码支持: Python3, JS,CPP

Python3 Code:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordDict = set(wordDict)
        @cache
        def dp(pos):
            if pos == len(s): return True
            cur = ''
            for nxt in range(pos, len(s)):
                cur += s[nxt]
                if cur in wordDict and dp(nxt + 1): return True
            return False
        return dp(0)

JS Code:

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const dp = Array(s.length + 1);
  dp[0] = true;
  for (let i = 0; i < s.length + 1; i++) {
    for (let word of wordDict) {
      if (word.length <= i && dp[i - word.length]) {
        if (s.substring(i - word.length, i) === word) {
          dp[i] = true;
        }
      }
    }
  }

  return dp[s.length] || false;
};

CPP Code:

class Solution {
public:
    bool wordBreak(string s, vector<string>& dict) {
        unordered_set<string> st(begin(dict), end(dict));
        int N = s.size();
        vector<bool> dp(N + 1);
        dp[0] = true;
        for (int i = 1; i <= N; ++i) {
            for (int j = 0; j < i && !dp[i]; ++j) {
                dp[i] = dp[j] && st.count(s.substr(j, i - j));
            }
        }
        return dp[N];
    }
};

复杂度分析

令 n 和 m 分别为字符串和字典的长度。

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

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。