Word Break [dp, j as first loop]

139.Word Break

Dynamic Programming

String

Hash Table

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.

Example:

Input:

s = "leetcode"
wordDict = ["leet","code"]

→

Output:

true

Return true because "leetcode" can be segmented as "leet code"

Algorithm:

1. Use DP array where dp[i] represents if s[0,i] can be segmented
2. For each index j, try to break string at every previous index i
3. Check if substring exists in dictionary and previous segment is valid
4. Use HashSet for O(1) word lookup

Complexity:

Time: O(n³) due to substring | Space: O(n) for DP array

Java Solution:

public boolean wordBreak(String s, List wordDict) {
    // DP array where dp[i] means s[0:i] can be segmented
    boolean[] dp = new boolean[s.length()];
    
    // Convert dictionary to HashSet for O(1) lookup
    Set word = new HashSet<>(wordDict);

    // Process each ending position
    for (int j = 0; j < s.length(); j++) {
        // Check if entire substring is a word
        if (word.contains(s.substring(0, j + 1))) {
            dp[j] = true;
            continue;
        }
        
        // Try to break string at each previous position
        for (int i = j; i >= 1; i--) {
            String sub = s.substring(i, j + 1);
            // Check if current substring is word and previous part is valid
            if (word.contains(sub) && dp[i - 1])
                dp[j] = true;
        }
    }
    
    return dp[s.length() - 1];
}

Python Solution:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    # DP array where dp[i] means s[0:i] can be segmented
    dp = [False] * len(s)
    word_set = set(wordDict)
    
    # Process each ending position
    for j in range(len(s)):
        # Check if entire substring is a word
        if s[:j + 1] in word_set:
            dp[j] = True
            continue
        
        # Try to break string at each previous position
        for i in range(j, 0, -1):
            sub = s[i:j + 1]
            if sub in word_set and dp[i - 1]:
                dp[j] = True
                break
                
    return dp[-1]

C++ Solution:

bool wordBreak(string s, vector& wordDict) {
    // DP array where dp[i] means s[0:i] can be segmented
    vector<bool> dp(s.length());
    unordered_set word_set(wordDict.begin(), wordDict.end());
    
    // Process each ending position
    for (int j = 0; j < s.length(); j++) {
        // Check if entire substring is a word
        if (word_set.count(s.substr(0, j + 1))) {
            dp[j] = true;
            continue;
        }
        
        // Try to break string at each previous position
        for (int i = j; i >= 0; i--) {
            string sub = s.substr(i, j - i + 1);
            if (word_set.count(sub) && dp[i - 1]) {
                dp[j] = true;
                break;
            }
        }
    }
    
    return dp.back();
}