---
title: 【LeetCode】0139. Word Break
date: 2018-12-21
is_modified: false
disqus: cynthiahackmd
categories:
- "面試刷題"
tags:
- "LeetCode"
---

{%hackmd @CynthiaChuang/Github-Page-Theme %}

<br>

Given a **non-empty** string _s_ and a dictionary _wordDict_ containing a list of **non-empty**words, determine if _s_ can be segmented into a space-separated sequence of one or more dictionary words.
<!--more-->
<br>

> **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.

<br>

**Example 1:**

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: True
Explanation:Return true because "leetcode" can be segmented as "leet code".

**Example 2:**

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: True
Explanation:Return true because "leetcode" can be segmented as "leet code".

**Example 3:**

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

<br>

**Related Topics:** `Dynamic Programming`

## 解題邏輯與實作
這題是要將題目給定的句子拆解成字典中的單字。第一個想到的就是我最愛的暴力法，拆、拆、拆就對了！

### 遞迴
也就是暴力解，想法很簡單，就是把句子拆成前後兩句下去查，一旦有一種拆法可以查的到就回傳 True，否則回傳 False。當然為了避免大量重複計算，另外用 HashTable 記錄查過得結果，解法如下：

1. 查詢此單字是否存在於字典中
1. 有，則回傳 True
2. 否，則向下執行
2. 使用一個指標由前向後遍歷此單字，並依指標位置，將單字拆成前後部份並呼叫遞迴傳入，唯有當前後部份皆可在字典中查到時才回傳 True，否則繼續向後遍歷。
3. 若遍歷完整個字串皆無法找到拆解法則回傳 False

class Solution:
      def __init__(self, mydict=None):
            self.mydict = mydict
            self.memo = {}

      def set_dict(self,mydict):
            self.mydict = mydict
            
      def wordBreak(self, s, wordDict):
            self.set_dict(set(wordDict))
            return self.check(s)

      def check(self, s):
            length = len(s)
            
            if s in self.memo:
                  return self.memo.get(s)

            if length <= 0 or s in self.mydict:
                  self.memo[s] = True
                  return True

            result = False
            for i in range(1, length):
                  result = self.check(s[:i]) and self.check(s[i:])
                  if result :
                        break

            self.memo[s] = result
            return result

但果不期然，效率有點差跑出了個 740 ms, 1.20% 的成績，摸摸鼻子改寫 DP 去。

### Dynamic Programming
這題大概是難得我這幾天整理的題目中，DP 解終於不是欠著的題目了 XDDD

這邊使用了一個 dp 陣列記錄結果，其中 dp[i] 中記錄著字串 s[:i] 是否能夠拆解，接下來若是 s[i:j] 也可以進行拆解，因為已知 s[:i] 可拆解，又s[i:j] 可拆解，故 s[:j] 可拆解，因此記錄 dp[j] 為 True，按這關係推導，最後就可以判斷目標字串是否可以被拆解。

class Solution:
      def wordBreak(self, s, wordDict):
            n = len(s)
            dp = [False] * (n + 1)
            dp[0] = True
      
            words = set(wordDict)
            for j in range(n):
                  for i in range(j, -1, -1):
                        if dp[i] and s[i:j + 1] in words:
                              dp[j + 1] = True
                              break
            return dp[n]

這效能果然好上不少，跑出了 68 ms, 15.49% 的成績。

### Dynamic Programming 改進版
看到我的 code 雖然有比上次進步，但其實無條件進位也才 16% 而已，有些好奇前面 code是怎樣的，所以手賤點了前段班的 code 出來看。

發現他雖然也是用 DP 解，但他加上了點巧思，與我不同的是他是由後向前遍歷，並寫加上了檢查距離的限制，限制在字典中最長的單字長度上，檢查再多也沒有意義，因為字典就沒有這麼長的單字咩。最後跑出來成績為 36 ms, 99.65% 。

class Solution:
      def wordBreak(self, s, wordDict):
            words = set(wordDict)
            maxLen = 0
            for word in wordDict:
                  maxLen = max(maxLen, len(word))
            n = len(s) 
            dp =   [False] * (n + 1)
            dp[n] = True 

            for i in range(n - 1, -1, -1):
                  for j in range(i + 1, min(i + maxLen, n) + 1): 
                        if dp[j] and s[i:j] in words:
                              dp[i] = True
                              break 
            return dp[0]

## 其他連結
1. [【LeetCode】0000. 解題目錄](/x62skqpKStKMxRepJ6iqQQ)

<br><br>

> **本文作者**： 辛西亞．Cynthia
> **本文連結**： [辛西亞的技能樹](https://cynthiachuang.github.io/LeetCode-0139-Word-Break) / [hackmd 版本](https://hackmd.io/@CynthiaChuang/LeetCode-0139-Word-Break)
> **版權聲明**： 部落格中所有文章，均採用 [姓名標示-非商業性-相同方式分享 4.0 國際](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en) (CC BY-NC-SA 4.0) 許可協議。轉載請標明作者、連結與出處！