Episode Overview

In this episode, we’ll walk through how to solve one of the most common string and dynamic programming problems asked in coding interviews: Leetcode 139 – Word Break.

You’ll learn how to determine whether a given string s can be split into a sequence of valid words found in a dictionary (wordDict). This problem is a classic example of applying Dynamic Programming to segment strings efficiently.

By the end of the episode, you will:

• Understand the core idea of prefix-based segmentation.

• Learn how to break the problem down into smaller subproblems using dynamic programming.

• See how to implement an optimized solution in C++ using unordered_set and a dp array.

What You’ll Learn

• How to use dynamic programming to solve string segmentation problems

• The meaning and role of each entry in the dp array

• How to iterate efficiently over all possible substring partitions

• How to use a hash set (unordered_set) for fast lookups

• How early termination improves performance

Problem Statement Recap

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

Example:
Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: The string can be split as "apple pen apple" where each word exists in the dictionary.

Code Walkthrough (C++)

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        vector<bool> dp(n + 1, false); // dp[i]: can s[0...i-1] be segmented?
        dp[0] = true; // Base case: empty string

        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n]; // Can the whole string be segmented?
    }
};

Step-by-Step Explanation

1. Define a DP array
   dp[i] means: Can the substring s[0..i-1] be segmented into dictionary words?
   Start with dp[0] = true since the empty string is always segmentable.

2. Convert the dictionary to a set
   Using an unordered_set helps with constant-time word lookups.

3. Nested loop structure
   The outer loop iterates over i from 1 to n.
   The inner loop tries all split points j such that if dp[j] is true and s[j...i-1] is a valid word, then dp[i] = true.

4. Break early
   Once a valid segmentation is found for a position i, there’s no need to keep checking other values of j.

5. Return result
   The answer is dp[n] — can the entire string s be segmented?

Time and Space Complexity

• Time Complexity: O(n²), due to the nested loop over all substring partitions.

• Space Complexity: O(n + m), where n is the length of s and m is the number of words in the dictionary.