Word Break | Engineering Interview Kit

Concept

LeetCode #139.
Problem: 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.

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true (Return true because “leetcode” can be segmented as “leet code”).

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

The DP Strategy

We use a 1D dp boolean array.
dp[i] will answer: “Can the substring of s up to index i be perfectly built using the dictionary?”

Let’s look at "leetcode".
Index 4 is "leet". That is in the dictionary! So dp[4] = true.
Now let’s look at index 8 ("leetcode").
We slice the end of the word: "code". "code" is in the dictionary!
BUT, that’s not enough. Just because "code" is valid, doesn’t mean the entire string is valid.
We MUST check if the string immediately prior to "code" was perfectly valid. We check dp[4]. dp[4] is true!
Because the prefix was valid, and the new slice is valid, dp[8] becomes true!

The Recurrence Rule:
If dp[j] is true (valid prefix), and s.slice(j, i) is in the dictionary, then dp[i] = true.

Implementation (Tabulation)

// Time Complexity: O(N^3) (Nested loops + String slicing)
// Space Complexity: O(N) (For the DP array)

function wordBreak(s: string, wordDict: string[]): boolean {
    // Put the dictionary into a Hash Set for O(1) instantaneous lookups
    const wordSet = new Set(wordDict);

    // dp[i] represents if s.slice(0, i) is valid.
    // The array length is s.length + 1 to include the empty string base case.
    const dp = new Array(s.length + 1).fill(false);
    
    // Base Case: An empty string "" is always perfectly valid.
    dp[0] = true;

    // Loop through every possible ending index
    for (let i = 1; i <= s.length; i++) {
        
        // Loop backwards to find a valid prefix!
        for (let j = 0; j < i; j++) {
            
            // Is the prefix up to j valid?
            if (dp[j] === true) {
                
                // Yes! Now, is the remaining slice from j to i in the dictionary?
                const wordSlice = s.slice(j, i);
                if (wordSet.has(wordSlice)) {
                    
                    // We found a perfect match! Mark i as valid.
                    dp[i] = true;
                    
                    // Optimization: We don't need to keep checking j's for this i!
                    break;
                }
            }
        }
    }

    // The last index holds the answer for the entire string
    return dp[s.length];
}

Time Complexity Analysis

Why is the Time Complexity $O(N^3)$ ?

The outer loop i runs $N$ times.
The inner loop j runs up to $N$ times. ( $N \times N = N^2$ ).
Inside the inner loop, s.slice(j, i) physically copies up to $N$ characters in RAM. That is an $O(N)$ operation inside an $O(N^2)$ loop! $N^2 \times N = N^3$ .

For standard LeetCode problems where $s$ is length 300, $300^3$ is 27 Million operations, which passes easily.

Interview Questions

Q: Can we optimize the inner loop to prevent the $O(N^3)$ time limit?
A: Yes. Notice that the inner loop j checks every single previous index. If the absolute longest word in the entire dictionary is 10 characters long, it is mathematically pointless to slice 50 characters backwards! You can find the maxLength of the words in the dictionary, and change the inner loop to only look backwards a maximum of maxLength steps (for let j = i - 1; j >= Math.max(0, i - maxLength); j--). This drops the time complexity to roughly $O(N^2)$ .

Q: A developer suggests using a Trie (Prefix Tree) instead of DP. Is this valid?
A: Yes, inserting the dictionary into a Trie and recursively traversing it with Memoization is an incredibly elegant and valid solution. It rapidly prunes impossible paths (if a character doesn’t exist in the Trie, abort immediately, completely avoiding the $O(N)$ string slicing overhead). DP and Trie+Memoization are both perfect $A+$ answers for Word Break.