🟨 Word Break (#139)

🔗 Problem Link

• LeetCode - Word Break
• NeetCode - Word Break

📋 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.

💡 Examples

Example 1

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

Example 2

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

Example 3

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

🔑 Key Insights & Approach

Core Observation: dp[i] = true if substring [0...i] can be segmented using wordDict.

Why DP?

• O(n² * m) time where m = avg word length
• O(n) space
• Check all possible word breaks

Pattern: "String Segmentation DP" pattern.

🐍 Solution: Python

Approach: Bottom-Up DP

Time Complexity: O(n² * m) | Space Complexity: O(n)

from typing import List

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

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

        return dp[len(s)]

🔵 Solution: Golang

Approach: DP

Time Complexity: O(n² * m) | Space Complexity: O(n)

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

    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)]
}

📚 References

• NeetCode - Word Break