【LeetCode】0140. Word Break II

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:

1
2
3
4
5
6
Input: s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output: [
  "cats and dog",
  "cat sand dog"
]

Example 2:

1
2
3
4
5
6
7
8
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:

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


Related Topics:Dynamic ProgrammingBacktracking



解題邏輯與實作

第二個例子,腦中瞬間出現這個旋律(想被洗腦的這邊走),上一題還沒注意到的說 XDDD

enter image description here

忽然覺得他的眼神有點鄙視……是我錯覺嗎( ˘•ω•˘ )


遞迴

好了,先別管古坂大魔王了,LeetCode 大魔王處理先。像這種找所有可能的題目,首先想到的是遞迴,更別說我在寫程式的時候,第一 round 偏好用暴力法,暴力法的雖然效能都不是很好,但它的寫法較為簡潔,適合拿來釐清思路,等寫出一個可以 round 的版本,我才會開始做效率的改進。這種作法有好有壞啦,端看大家的習慣怎樣。

基本上在做的時候還是在拆、拆、拆, 如果字串前半有在字典當中,就把後半部傳入遞迴再做拆解,如果後半也拆的開,,就回傳回去做文字的拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from collections import defaultdict
class Solution(object):
      def __init__(self):
            self.memo   = defaultdict(list)
            self.mydict = None

      def set_dict(self,mydict):
            self.mydict = set(mydict)

      def wordBreak(self, s, wordDict):
            self.set_dict(wordDict)
            return self.recursive(s)		

      def recursive(self,s):
            if not s:
                  return [None]

            if s in self.memo:
                  return self.memo[s]

            res = []
            for word in self.mydict:
                  n = len(word)
                  if s[:n] != word:
                        continue
                        
                  for r in self.recursive(s[n:]):
                        result = word + " " + r if r is not None else word
                        res.append(result)
                        
            self.memo[s] = res
            return res


DAG

話說在寫這題的時候,越寫越覺得超級像中文斷詞的,只是不需要做到最後一步,在中間就可以回傳中間產物了。以 Jieba 斷詞演算法(雖然我慣用的斷詞API不是 Jieba XDDD)來說,他在第一個步驟會建立 Trie 與 DAG 資料結構,快速算出所有合法的切分組合,就只需要做到這裡就好,第二部份的統計模型計算可以先忽略它。

我有按照個想法時做了一版,但…它目前還只是個屍體而已… Orz



其他連結

  1. 【LeetCode】0000. 解題目錄