Word Break medium

Problem Statement

Given a string s and a dictionary of strings wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1

  • Input: s = "leetcode", wordDict = ["leet","code"]
  • Output: true
  • Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2

  • Input: s = "applepenapple", wordDict = ["apple","pen"]
  • Output: true
  • Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".

Steps

  1. Dynamic Programming Approach: We'll use dynamic programming to solve this problem. Create a boolean array dp of size s.length + 1. dp[i] will be true if the substring s.substring(0, i) can be segmented into words from wordDict, and false otherwise.

  2. Base Case: dp[0] = true (empty string can always be segmented).

  3. Iteration: Iterate through the string s from index 1 to s.length. For each index i, check if the substring s.substring(j, i) (where j ranges from 0 to i - 1) is in wordDict. If it is, and dp[j] is true (meaning the substring from 0 to j can be segmented), then set dp[i] to true.

  4. Result: dp[s.length] will contain the final result. If it's true, the string can be segmented; otherwise, it cannot.

Explanation

The dynamic programming approach builds up a solution iteratively. It considers each prefix of the input string and checks if it can be segmented based on previously solved subproblems. The dp array stores the results of these subproblems, avoiding redundant calculations. This significantly improves efficiency compared to a naive recursive approach.

Code

function wordBreak(s: string, wordDict: string[]): boolean {
    const n = s.length;
    const dp: boolean[] = new Array(n + 1).fill(false);
    dp[0] = true; // Base case: empty string is always segmented

    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            const word = s.substring(j, i);
            if (wordDict.includes(word) && dp[j]) {
                dp[i] = true;
                break; // Optimization: Once we find a segmentation, no need to check further for this 'i'
            }
        }
    }

    return dp[n];
}

Complexity

  • Time Complexity: O(n^2 * m), where n is the length of the string s and m is the length of wordDict. The nested loops dominate the time complexity. The includes() method on an array has a time complexity of O(m) in the worst case.
  • Space Complexity: O(n), due to the dp array. The space used by wordDict is considered constant.