0139. Word Break

leetcode

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.

Solution Description

To implement a solution for this problem, we need to use a dynamic programming approach. We will create a boolean array dp where dp[i] indicates whether the substring s[0:i] can be segmented into valid dictionary words. The array will be initialized with false, except for dp[0] which will be true since an empty string can always be segmented.

Iterate over the string s with an index i.
For each position i, iterate again with an index j such that 0 < j < i=.
Check if the substring s[j:i] exists in wordDict and dp[j] is true. If both conditions are satisfied, set dp[i] to true.
Finally, return dp[n] where n is the length of the string s.

The time complexity of this approach is O(n * m) where n is the length of the string s and m is the maximum length of the words in the dictionary. The space complexity is O(n) due to the dp array.

Example

Let's assume s is "leetcode" and wordDict contains ["leet", "code"].

Initialize dp as [true, false, false, false, false, false, false, false, false].
Iterate over s:
- i = 1 to 8:
  - For i = 4: Substring = "leet" is in wordDict and dp[0] is true. So, dp[4] becomes true.
  - For i = 8: Substring = "code" is in wordDict and dp[4] is true. So, dp[8] becomes true.
dp[8] is true, so the function returns true.

References

Dynamic Programming: https://en.wikipedia.org/wiki/Dynamic_programming
LeetCode problem description: 139. Word Break

Solution

Submission: 2024-09-18 Word Break - Submission Detail - LeetCode leetcode.com

Here’s the implementation of the solution along with the test cases:

/**
 * @param {string} s - The input string to be segmented.
 * @param {string[]} wordDict - The dictionary containing valid words.
 * @return {boolean} - Returns true if s can be segmented into a sequence of words in wordDict.
 */
function wordBreak(s, wordDict) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;


    const wordSet = new Set(wordDict);
    const n = s.length;
    const canBreak = Array(n + 1).fill(false);
    canBreak[0] = true;

    log(`s=${s}`);
    log(`wordDict=${wordDict}`);

    for (let wend = 1; wend <= n; wend++) {
        for (let wstart = 0; wstart < wend; wstart++) {
            const word = canBreak[wstart] && s.substring(wstart, wend);
            log(`#wstart='${wstart}'; #wend='${wend}'; #word='${word}'`);
            if (wordSet.has(word)) {
                canBreak[wend] = true;
                break;
            }
        }
    }

    return canBreak[n];
}

// Test casesxo
const testCases = [
    { s: "leetcode", wordDict: ["leet", "code"], expected: true },
    { s: "applepenapple", wordDict: ["apple", "pen"], expected: true },
    { s: "catsandog", wordDict: ["cats", "dog", "sand", "and", "cat"], expected: false },
    { s: "aaaaaaa", wordDict: ["aaaa","aaa"], expected: true },
    { s: "abcd", wordDict: ["a","abc","b","cd"], expected: true },
];

testCases.forEach((test, index) => {
    const result = wordBreak(test.s, test.wordDict);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});