Medium — Dynamic Programming | String | Hash Table

The Problem

Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Approach

Uses dynamic programming where dp[i] represents whether the substring s[0:i] can be broken into valid words. For each position, it checks all possible word endings by looking at previous valid breakpoints.

Time: O(n²) · Space: O(n)

Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # Create a set for faster word lookup.
        wordSet = set(wordDict)

        # Initialize a boolean array dp where dp[i] is True if s[0:i] can be broken into words.
        dp = [False] * (len(s) + 1)
        dp[0] = True  # An empty string can always be broken.

        # Iterate through the string.
        for i in range(1, len(s) + 1):
            for j in range(i):
                # Check if the substring s[j:i] is in the wordDict and if s[0:j] can be broken.
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break  # No need to continue checking.

        return dp[len(s)]

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment