DP Partitioning Feasibility¶
Table of Contents¶
- 2369. Check if There is a Valid Partition For The Array (Medium)
- 139. Word Break (Medium)
2369. Check if There is a Valid Partition For The Array¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, dynamic programming
139. Word Break¶
-
LeetCode | LeetCode CH (Medium)
-
Tags: array, hash table, string, dynamic programming, trie, memoization
139. Word Break - Python Solution
from typing import List
# DP (Unbounded Knapsack)
def wordBreak(s: str, wordDict: List[str]) -> bool:
n = len(s)
dp = [False for _ in range(n + 1)]
dp[0] = True
for i in range(1, n + 1):
for word in wordDict:
m = len(word)
if s[i - m : i] == word and dp[i - m]:
dp[i] = True
return dp[-1]
s = "leetcode"
wordDict = ["leet", "code"]
print(wordBreak(s, wordDict)) # True