Leetcode # 139. Word Break

https://leetcode.com/problems/word-break/

Dynamic Programming

Time Complexity: O(len(s) ^ 3)
Space Complexity: O(len(s))

※ 上述複雜度也能以 Recursion wt/ Memoization
或 Depth-First Search（以 word 為節點單位）達成

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

Last Updated on 2023/08/16 by A1go