【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 Programming、Backtracking

解題邏輯與實作

第二個例子，腦中瞬間出現這個旋律（想被洗腦的這邊走），上一題還沒注意到的說 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. 解題目錄