Code › algorithm-study

LeetCode 139 - Word Break

A Python dynamic programming solution for checking whether a string can be segmented by a word dictionary

algorithmleetcodedynamic-programmingstringpythonlearning

This is a Medium dynamic programming problem. Given a string s and a dictionary wordDict, the task is to decide whether the whole string can be segmented into dictionary words. I could not derive the solution on my own this time, and after reading a solution, the main idea I learned was to use the DP array as a set of reachable checkpoints.

  • Problem link: 139. Word Break
  • Summary: Given a string s and a word dictionary wordDict, return true if s can be built by concatenating one or more words from the dictionary. The same word may be reused multiple times.

For example, if s is leetcode and wordDict is ["leet", "code"], the answer is true because the string can be split into leet and code. If s is catsandog with words such as cats, dog, sand, and, and cat, the answer is false because no split covers the entire string.

Approach

At first, I did not find the right rule for where to cut the string. It felt possible to try matching words from the front or from the back, but I could not turn that into a condition that preserved the remaining possibilities.

The solution made the state definition clearer. dp[i] means that the prefix ending right before index i, or s[:i], can be built from words in wordDict. The DP array is one element longer than the string, and dp[0] starts as true because the empty prefix is the starting checkpoint.

dp = [False] * (s_len + 1)
dp[0] = True

Without dp[0], there is no valid place for the first word to start. For example, to accept s[0:4] when leet is in the dictionary, the split index j must be 0 and dp[0] must already be true. This does not mean the empty string is being treated as a dictionary word. It only opens the initial checkpoint.

Then the algorithm increases i from 1 through the length of the string and looks for the last word ending at i. The index j is the split point where that last word begins. If dp[j] is true, then s[:j] is already buildable. If s[j:i] is also in word_set, then s[:i] becomes buildable as well.

for i in range(1, s_len + 1):
    for j in range(i):
        if dp[j] and s[j:i] in word_set:
            dp[i] = True

So the problem is not solved by choosing one full split upfront. It is solved by marking positions that can be reached from earlier valid positions. Any index where dp[j] is true can act as a checkpoint for the next word.

The dictionary is converted to a set so membership checks are fast on average. If the code searched through the original list each time, each lookup would also depend on the number of words. The set helps with lookup, but it does not remove the cost of Python slicing.

Troubleshooting

The most important correction for me was that dp[i] is not about whether one word is valid. It means the whole prefix s[:i] is valid. Even if the last piece s[j:i] exists in the dictionary, that split is unusable when the earlier prefix s[:j] cannot be built.

That is why the condition has to check both parts together: dp[j] and s[j:i] in word_set. A dictionary word only helps when it starts from a checkpoint that has already been reached.

The other point was complexity. The nested loops make the solution look like O(n²), but s[j:i] creates a new string in Python. That slicing operation takes time proportional to the substring length, and the set lookup for the newly created string also needs its hash. Across all pairs of i and j, those substring lengths add up to O(n³).

Complexity analysis

  • Time complexity: O(n³ + L)

    • n is the length of s, and L is the total number of characters in wordDict. Building word_set takes O(L). The DP loops inspect O(n²) pairs of j and i, and each check creates and hashes s[j:i], whose cost is proportional to the substring length. Summed across all substrings, that gives O(n³).

  • Space complexity: O(n + M)

    • M is the number of words in wordDict. The DP array stores one boolean per string position, and word_set stores O(M) references to the existing string objects. A temporary slice can be as long as O(n), so the auxiliary space is O(n + M).

Implementation code

from typing import List

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        s_len = len(s)
        dp = [False] * (s_len + 1)
        dp[0] = True

        for i in range(1, s_len + 1):
            for j in range(i):
                if dp[j] and s[j:i] in word_set:
                    dp[i] = True

        return dp[-1]

Summary and reflection

I did not get to this DP state definition by myself. After reading the solution, the key idea was to define dp[i] as whether the prefix s[:i] is buildable, then use every true DP entry as a checkpoint for the next word.

Once dp[0] is understood as the starting checkpoint and j as the start of the last word, the code becomes compact. The complexity analysis still needs care, though. In Python, slicing inside the nested loop is part of the runtime, so the solution is O(n³), not just O(n²). This was a useful reminder that the DP structure and the language-level operation cost both matter.