NUHMAN.com

Introduction

LeetCode 139: Word Break is a classic dynamic programming (DP) problem where you're given a string and a dictionary of words, and you need to determine whether the string can be segmented into a space-separated sequence of one or more dictionary words.

This problem is fundamental to understanding DP on strings and solving problems involving substring matching and memoization.

Problem Statement

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.

Each word in wordDict can be used multiple times.

Example

go

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: "leetcode" = "leet" + "code"
go

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
go

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

Approach

We use Dynamic Programming (DP) to solve this efficiently.

✅ Steps:

1. Initialize a boolean DP array of size len(s)+1. dp[i] means whether s[:i] can be segmented.
2. Set dp[0] = true, meaning an empty string is always segmentable.
3. For every i from 1 to len(s), check all possible previous positions j (from 0 to i).

• If dp[j] is true and s[j:i] is in the dictionary, set dp[i] = true.

Go Implementation

go

package main

import (
    "fmt"
)

func wordBreak(s string, wordDict []string) bool {
    wordSet := make(map[string]bool)
    for _, word := range wordDict {
        wordSet[word] = true
    }

    dp := make([]bool, len(s)+1)
    dp[0] = true // Empty string can always be segmented

    for i := 1; i <= len(s); i++ {
        for j := 0; j < i; j++ {
            if dp[j] && wordSet[s[j:i]] {
                dp[i] = true
                break
            }
        }
    }

    return dp[len(s)]
}

Time and Space Complexity

MetricComplexityTime ComplexityO(n²)Space ComplexityO(n + k)

• n is the length of the string s.
• k is the total number of characters in wordDict.

The nested loop makes the time complexity O(n²), but it's acceptable for typical inputs.

Why This Works

• The DP array keeps track of segmentability up to each index.
• For each possible split point j, we only check if the remaining substring is in the dictionary.
• HashMap lookup (wordSet) ensures fast substring match checking.

Edge Cases

• s is empty → return true
• wordDict is empty → return false (unless s is empty)
• Words in dictionary may repeat or overlap

Conclusion

LeetCode 139: Word Break is a staple problem to master for interviews and building a foundation in DP on strings. It challenges you to think about prefixes, substring matching, and how to optimize solutions with memoization or tabulation.