Skip to content

Latest commit

 

History

History
169 lines (132 loc) · 3.69 KB

0140._word_break_ii.md

File metadata and controls

169 lines (132 loc) · 3.69 KB

140. Word Break II

难度: Hard

刷题内容

原题连接

内容描述

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]
Example 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.
Example 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

解题方案

思路 1 - 时间复杂度: O(len(s)^2)- 空间复杂度: O(1)******

dfs, 超时

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        res = []
        def dfs(idx, tmp_res):
            if idx == len(s):
                res.append(tmp_res[:-1])
            for i in range(idx+1, len(s)+1):
                if s[idx:i] in wordDict:
                    dfs(i, tmp_res+s[idx:i]+' ')
        dfs(0, '')
        return res

思路 2 - 时间复杂度: O(len(s)^2)- 空间复杂度: O(len(s)^2)******

把word break i 结合起来减少时间复杂度的作法。

做法如下，聪明：

就是对于每一个s，我们来check它是否可以break，如果不可以，就不用做相应的操作了

但是其实

s = "aaaaaa"
wordDict = ["a","aa","aaa"]
还是会loop很多次

不过像
s = "aabbb"
wordDict = ["a","abbb"]
就会减少很多loop次数

beats 10.10%

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        res = []
        
        def dfs(idx, tmp_res):
            if idx == len(s):
                res.append(tmp_res[:-1])
            if not self.check(s[idx:], wordDict):
                return
            for i in range(idx+1, len(s)+1):
                if s[idx:i] in wordDict:
                    dfs(i, tmp_res+s[idx:i]+' ')
                    
        dfs(0, '')
        return res
    
    def check(self, s, wordDict):
        ok = [True]
        for i in range(1, len(s) + 1):
            ok += any(ok[j] and s[j:i] in wordDict for j in range(i)),
        return ok[-1]

思路 3 - 时间复杂度: O(len(wordDict) * len(res))- 空间复杂度: O(len(s)^2)******

可以用cache加快速度，beats 89.77%

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """
        return self.helper(s, wordDict, {})
    
    def helper(self, s, wordDict, memo):
        if s in memo: 
            return memo[s]
        if not s: 
            return []

        res = []
        for word in wordDict:
            if not s.startswith(word):
                continue
            if len(word) == len(s):
                res.append(word)
            else:
                resultOfTheRest = self.helper(s[len(word):], wordDict, memo)
                for item in resultOfTheRest:
                    item = word + ' ' + item
                    res.append(item)
        memo[s] = res
        return res