Skip to content

Trie Optimized DP

Table of Contents

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

140. Word Break II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, hash table, string, dynamic programming, backtracking, trie, memoization

472. Concatenated Words

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, string, dynamic programming, depth first search, trie

2977. Minimum Cost to Convert String II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, string, dynamic programming, graph, trie, shortest path

Comments