Crack the Backend

Problem Statement

Given a string s and a list of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same word may be reused multiple times. Return false if no such segmentation exists.

We only need to decide reachability (can we segment the whole string?), not output the actual segmentation.
Putting wordDict in a Set gives O(1) lookup for substrings.

Key Observations

Define dp[i] = can we segment the prefix s[0..i) (length i) using the dictionary? Then dp[i] is true iff there exists j in [0, i-1] such that dp[j] is true and s.substring(j, i) is in the dictionary.
Base: dp[0] = true (empty prefix). For i from 1 to n, try every split j: if dp[j] and s[j..i) in dict, set dp[i] = true.
Use a Set for wordDict to check substrings in O(1).

Approach

High-level: dp[i] = can we segment s[0..i)? For each i, try all j < i: if dp[j] and s.substring(j, i) is in wordDict, set dp[i] = true. Return dp[n].

Steps:

Set<String> set = new HashSet<>(wordDict). dp[0] = true.
For i = 1..n: dp[i] = false; for j = 0..i-1, if dp[j] and set.contains(s.substring(j, i)), set dp[i] = true, break.
Return dp[n].

Implementation

Java

public boolean wordBreak(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && set.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length()];
}

Test Cases

Example 1

Input

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

Expected

true

Explanation

"leet code".

Complexity Analysis

Time: O(n^2 * word length) with set lookup.
Space: O(n).

Follow-ups

Word Break II: return all possible segmentations.