iT邦幫忙

2024 iThome 鐵人賽

DAY 6
0

今天我們繼續看一題字串類型的題目:拆字。

🟨拆字

本題取自 Leetcode 139. Word Break

題目

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

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 "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.


Example 3:

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

Constraints:

1 <= s.length <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

分析

題目給出一個字串以及一個包含許多字串的陣列,要我們判定字串能不能拆解成全由陣列內的字串所構成的片段。

分治法

我們以Example3為例來思考如何拆解問題為更小的子問題:

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

從字尾開始觀察,我們會發現,可以拆出'dog'

'dog'從字尾切掉之後剩下'catsan',再繼續思考能不能拆出字典中的字串。

依此類推一直往下拆解下去,若能找到一個能夠完全拆開的方式,就回答True,若不能,就回答False

設計狀態、找出轉移式與最小問題

我們可以用「剩餘的子字串開頭的index」來描述子問題。

狀態breakable(i):布林值,描述s[i:]能/不能完全拆解成字典內的字

狀態轉移式:前述的討論若寫成邏輯,會稍微複雜一點:

len(s) >= j > i範圍內存在一個j,使得breakable(j) == True ,且 s[i:j]是一個wordDict內的字串,則breakable(i)True。反之,則為False

如下圖:

alt text

最小子問題(邊界條件):

我們讓breakable(len(s))True,因為這代表字串s恰好切完了不剩任何字母。

母問題(題目所求):breakable(0),即詢問整個原始字串s是否可分割。

實作

Top-Down DP

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 把List轉化為Set,減少查詢時間
        wordSet = set(wordDict)

        # 子問提:s[i:]是否可拆分成...
        @cache
        def breakable(i):
            # 邊界條件:s已完全拆分(剩下空字串)
            if i==len(s): return True

            # 狀態轉移式
            return any(breakable(j) and s[i:j] in wordSet for j in range(i+1,len(s)+1) )
        
        # 母問題:s[0:] == s 是否可拆分成...
        return breakable(0)

子問題可能重複問到,因此要使用@cache或者手動快取計算過的子問題答案

此外還有幾個細節:

  • Hashmap的使用:

    • 測資給的wordDict是一個List(而非HashmapDict),這將導致每一次檢查s[i:j]存不存在於wordDict都花費O(n)的時間複雜度。在worst case(s不包含任何一個wordDict內的字串)時,演算法會對所有的s[i:j](即s的所有子字串)都進行檢查,因此降低這個檢查的複雜度是必要的。
    • 因此我們花費O(n)的時間將wordDict轉化為set,這個Python內建的資料型態可以看成空值的HashMap,讓每一次s[i:j] in wordSet的檢查都加快至O(1)
  • 高階函式any()

    any輸入一個可迭代物件,當其中的任何一個元素為True,則返回True。否則返回False

    其中的邏輯剛好就是轉移式中「若可以找到至少一個j,使得...,則為True」

    當然也可以手刻一個出來:

    def any(iterable):
        for item in iterable:
            if item: return True
        return False
    

Bottom-Up DP

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 把List轉化為Set,減少查詢時間
        wordSet = set(wordDict)
        
        # 記錄答案用的陣列,dp[i] == breakable(i)
        dp = [False] * len(s) + [True]

        # 從小問題(短的尾巴)開始往前計算
        for i in reversed(range(len(s))):
            dp[i] = any(dp[j] and s[i:j] in wordSet for j in range(i+1, len(s)+1))

        # 回答母問題    
        return dp[0]

由於和Top-Down使用了相同的轉移式,我們思考母問題時,把原始字串從前面開始拆分,所以要從後面(最小的問題)開始計算。

當然也可以從前往後計算,不過子問題和轉移式就要對應著做修改。各位讀者有興趣的話也可以練習看看。

複雜度分析

時間複雜度

建立Hashmap的部分:時間複雜度為O(m)m = len(wordDict)

動態規劃的部分

時間複雜度 = 狀態轉移數 x 計算複雜度

本題的狀態數 = O(n)n = len(s)

計算複雜度的討論有一點複雜:

若將「s不包含wordSet內任何一個字串」視為worst case討論,因此any總是檢查完所有的j,才會返回False,又因為所有的dp[j]均為Falseany內每個j檢查的複雜度為O(1),因此,每個狀態的總計算複雜度為O(n)

因此總時間複雜度 = O(m + n^2)

空間複雜度

建立wordSet需要O(m)空間,m為wordDict的長度

後續紀錄答案需要O(n)空間

因此總空間複雜度O(m + n)

DFS

本題還有另一個思考的角度:

  • 將字串s上的每一個字母都當成是一個節點
  • s[i:j]存在於wordDict內,則(i,j)節點間存在一個連結
  • 原題目則等同於:節點0與節點len(s)+1是否連通。

例如 s = "catsandogs", wordDict = ["cats","dogs","sand","and","cat"] 等價於下圖:

alt text

由於開頭的c結尾並不連通,這個例子答案為false。

從這個角度出發,原題等價於「求一個圖(graph)中的某兩個節點(node)是否連通」,其實就是我們在Day5(費氏數列扒手題型)介紹過的Depth First Search問題。

至於寫出來的程式碼,則和動態規劃殊途同歸,因為「檢查兩個節點是否連通」的程式邏輯就是我們在前述動態規劃時檢查s[i:j]是否存在於wordDict當中的程式碼!

結語

字串和List都能用index取值,因此大多數的情況下都可以用1-D DP的框架來思考如何分治,設定狀態並找到子問題。

如果苦無切入點時,以簡單的測資作為出發點,畫圖思考題目的情境,對於解題會相當有幫助!

此外,本題的材料明明就是字串,但是從另一個角度切入,又和費氏數列題型的問題有相似之處。希望各位讀者也能從中體驗到動態規劃題型「異曲同工」背後共通的核心思維!


以上為Day10的內容!感謝你的閱讀,如果有不同的想法或心得,歡迎留言一同討論!

本文也同步登載在我的個人部落格,記錄我的學習筆記與生活點滴,歡迎來逛逛。

明天會繼續看其他的字串題。


上一篇
Day 09 字串題型(一) 最長的回文子字串(LPS)
下一篇
Day 11 字串題型(三) 最長的共同子序列(LCS)
系列文
刷題小白與Python的動態規劃之旅13
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言