Leetcode # 139. Word Break

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

Solution

dp[i] := ∃ j < i s.t. dp[j] == True and s[j:i] in words
dp[0] := True

n := len(s)
m := len(wordDict)
k := max([len(w) for w in wordDict])

Time Complexity: O(n * m * k)
Space Complexity: O(n)
(The input and output generally do not count towards the space complexity.)

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

Last Updated on 2023/08/16 by A1go