iT邦幫忙

0

【小馬的LeetCode練功坊】139, 140 Word Break,依單字清單斷句

參考題目: 140. Word Break II
題意: 給你一個字串和文字清單,回傳所有可能的斷句,
例如:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
(文字清單內的字可重複使用)

看到這個窮舉所有可能的問題,
直覺上想到的就是遞迴解,
檢查字串的開頭是否為文字清單的字

例如說:

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

"catsanddog"為"cats"與"cat"的開頭,
「"catsanddog"的所有分解」就可以遞迴地拆解成
"cats"與「"anddog"的所有分解」+ "cat"與「"sanddog"的所有分解」,
於是我寫了一個非常簡單的程式版本

純遞迴- 超時

class Solution:
   def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
       res = []
       for word in wordDict:
           if s.startswith(word):
               res += [s] if s==word else [word+' '+seg for seg in self.wordBreak(s[len(word):], wordDict)]
       return res

其實這一題的技巧是不要做重複的運算,
同一個字串有可能呼叫wordBreak()函數多次,
因此需要用python裡的dict,
如果答案已經計算過,
就直接調用之前的答案

用dict記錄答案- AC

class Solution:
   def __init__(self):
       self.wordMap = {}
       
   def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
       res = []
       for word in wordDict:
           if s.startswith(word):
               tail_word = s[len(word):]
               if tail_word in self.wordMap:
                   res += [word+' '+seg for seg in self.wordMap[tail_word]]
               else:
                   res += [s] if s==word else [word+' '+seg for seg in self.wordBreak(tail_word, wordDict)]
       self.wordMap[s] = res
       return res

尚未有邦友留言

立即登入留言