Word Break - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT_START = 'current_start', CURRENT_START_COLOR = 'gold';
const CURRENT_END   = 'current_end',   CURRENT_END_COLOR   = 'blue';

function visMainFunction(inputString, wordDict) {
    if (inputString.length === 0 || wordDict.length === 0) {
        notification("⚠️ <b>Invalid input detected.</b> Ensure that both the string and the dictionary contain valid values before running the algorithm.");
        return;
    }

    initClassProperties();

    // 🚀 Optimization: limit how far back and forward we look based on word lengths
    const [minWordLen, maxWordLen] = getWordLengthBounds(wordDict);

    startBatch();
    const wordSet = new VisSet(wordDict);

    const dp = new VisArray(inputString.length + 1).fill(false).options({ label: 'Word Break DP Table' });
    dp[0] = true; // Base case: an empty string is always a valid segmentation

    const s = VisArray.from([...inputString]);
    endBatch();

    explanationAndColorSchemaNotifications();

    // ⏩ Start from the smallest possible end index that could close a valid word
    let substringExclusiveEndIndex = Math.max(1, minWordLen);
    
    makeVisVariable(substringExclusiveEndIndex).registerAsIndexPointer(s, CURRENT_END);

    notification(`
      🔍 The goal is to determine if the string <b>"${inputString}"</b> 
      can be segmented into valid words from the dictionary.<br/><br/>
      📘 We will use <b>Dynamic Programming (DP)</b> where 
      <code>dp[substringExclusiveEndIndex]</code> indicates whether the substring 
      <code>s[0:substringExclusiveEndIndex]</code> (end is <b>exclusive</b>) can be segmented using dictionary words.<br/><br/>
      ⚙️ <b>Base Case:</b> <code>dp[0] = true</code> because an <b>empty string</b> can always be segmented 
      (it requires no words).<br/>
      As we progress, each <code>dp[substringExclusiveEndIndex]</code> depends on whether there exists an index 
      <code>substringStartIndex &lt; substringExclusiveEndIndex</code> such that 
      <code>dp[substringStartIndex]</code> is <b>true</b> 
      and <code>s[substringStartIndex:substringExclusiveEndIndex]</code> (end is exclusive) 
      is a valid word from the dictionary.<br/><br/>
      ▶️ We start checking from <code>substringExclusiveEndIndex = ${Math.max(1, minWordLen)}</code> 
      (the smallest possible end that can complete a word).<br/><br/>
      ⚡ <b>Optimization:</b> we only consider substrings whose lengths are between 
      <code>${minWordLen}</code> and <code>${maxWordLen}</code>, 
      since no dictionary word is shorter or longer than that.
    `);

    while (substringExclusiveEndIndex <= inputString.length) {
        // Use both max and min word length limits
        const startLowerBound = Math.max(0, substringExclusiveEndIndex - maxWordLen);
        const startUpperBound = substringExclusiveEndIndex - minWordLen;

        notification(`
            🔄 Checking if the substring until index <b>${makeColoredSpan(substringExclusiveEndIndex, CURRENT_END_COLOR)}</b> 
            of <b>"${inputString}"</b> can be segmented using dictionary words.<br/>
            - We only consider substrings whose lengths fall between 
              <code>${minWordLen}</code> and <code>${maxWordLen}</code>.<br/>
            - If <code>dp[substringStartIndex] = true</code>, it means that the first <b>substringStartIndex</b> characters can already be segmented.<br/>
            - Therefore, we check <b>${makeColoredSpan('substringStartIndex', CURRENT_START_COLOR)}</b> values in 
              <code>[${startLowerBound}, ${Math.max(startUpperBound, 0)})</code>.<br/>
            - If <code>dp[substringStartIndex] = true</code> and 
              <code>s[substringStartIndex:${substringExclusiveEndIndex}]</code> (end-exclusive) is in the dictionary, then 
              <code>s[0:${substringExclusiveEndIndex}]</code> (the first <b>${substringExclusiveEndIndex}</b> characters, end-exclusive) can be segmented, 
              so we set <code>dp[${substringExclusiveEndIndex}] = true</code>.
        `);

        let substringStartIndex = startLowerBound;
        makeVisVariable(substringStartIndex).registerAsIndexPointer(s, CURRENT_START);

        while (substringStartIndex <= startUpperBound) {
            startPartialBatch();
            const substring = inputString.substring(substringStartIndex, substringExclusiveEndIndex);

            notification(`📌 Checking substring <b>"${substring}"</b> 
                from index <b>${makeColoredSpan(substringStartIndex, CURRENT_START_COLOR)}</b> 
                to <b>${makeColoredSpan(substringExclusiveEndIndex - 1, CURRENT_END_COLOR)}</b>.`);

            if (dp[substringStartIndex] && wordSet.has(substring)) {
                notification(`✅ <b>Found valid segmentation!</b><br/>
                    - <b>"${substring}"</b> is in the dictionary.<br/>
                    - <code>dp[${substringStartIndex}] = true</code> indicates that the substring before it 
                      (<code>0..${substringStartIndex - 1}</code>) can be segmented.<br/>
                    - Thus, the first <b>${substringExclusiveEndIndex}</b> characters 
                      (<code>0..${substringExclusiveEndIndex - 1}</code>) as well can be segmented.<br/>
                      Setting <code>dp[${substringExclusiveEndIndex}] = true</code>.`);
                dp[substringExclusiveEndIndex] = true;
                break;
            } else {
                notification(`❌ <b>"${substring}"</b> is <b>not</b> in the dictionary or 
                    <code>dp[${substringStartIndex}]</code> is <b>false</b>, so we continue checking.`);
            }

            substringStartIndex += 1;
            endBatch();
        }

        substringStartIndex = -1; // just for the sake of animation, not part of the actual algorithm
        substringExclusiveEndIndex += 1;
    }

    if (dp[inputString.length]) {
        notification(`🏁 <b>Success!</b> The string <b>"${inputString}"</b> can be segmented into dictionary words.`);
    } else {
        notification(`❌ <b>Failed!</b> The string <b>"${inputString}"</b> cannot be fully segmented.`);
    }

    return dp[inputString.length];
}

function getWordLengthBounds(wordDict) {
    let minLen = Infinity;
    let maxLen = 0;

    for (const word of wordDict) {
        const len = word.length;
        if (len < minLen) minLen = len;
        if (len > maxLen) maxLen = len;
    }

    return [minLen, maxLen];
}

function initClassProperties() {
    setClassProperties(CURRENT_START, { backgroundColor: CURRENT_START_COLOR });
    setClassProperties(CURRENT_END, { backgroundColor: CURRENT_END_COLOR });
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();

  notification(`
    🎨 <b>Color & Legend</b><br/>
    • ${makeColoredSpan('substringStartIndex', CURRENT_START_COLOR)} — current <b>start</b> index we are testing.<br/>
    • ${makeColoredSpan('substringExclusiveEndIndex', CURRENT_END_COLOR)} — current <b>end</b> index (end is <b>exclusive</b>) we are testing.<br/>
  `);
}

Approach

Approach (Dynamic Programming — End-Exclusive Prefixes with Length Bounds Optimization)

We solve the Word Break problem using Dynamic Programming (DP) over end-exclusive prefixes of the input string. Let the input string be s and the dictionary be wordDict. We define a boolean array dp of length m + 1 (where m = s.length) such that:

dp[substringExclusiveEndIndex] is true if and only if the substring s[0:substringExclusiveEndIndex] (end is exclusive) can be segmented into valid dictionary words.

Initialization

Build a hash set wordSet from wordDict for O(1) average lookup time.
Compute the minimum and maximum word lengths in the dictionary:
• minWordLen = min(len(w)) for w ∈ wordDict
• maxWordLen = max(len(w)) for w ∈ wordDict
This allows us to ignore substrings that are too short or too long to match any valid word.
Initialize the boolean array dp with all values set to false.
Set the base case dp[0] = true, representing that the empty string can always be segmented.

Iteration Logic

We iterate over all possible end-exclusive indices of the string that could end a valid word:

For each substringExclusiveEndIndex from max(1, minWordLen) to m:
- Restrict the range of possible start indices using the known word length bounds:
  startLowerBound = max(0, substringExclusiveEndIndex - maxWordLen)
  startUpperBound = substringExclusiveEndIndex - minWordLen
- For each substringStartIndex in [startLowerBound, startUpperBound]: if dp[substringStartIndex] = true (meaning s[0:substringStartIndex], end-exclusive, can be segmented) and s[substringStartIndex:substringExclusiveEndIndex] (end-exclusive) exists in wordSet, we can also segment s[0:substringExclusiveEndIndex] (end-exclusive).
- Once such a substring is found, we set dp[substringExclusiveEndIndex] = true and skip further checks for this index.

Final Result

After completing all iterations, dp[m] (where m = s.length) represents whether the entire string s can be segmented into valid dictionary words. If dp[m] = true, segmentation is possible; otherwise, it is not.

Time Complexity

Let m = s.length and define rangeLen = maxWordLen - minWordLen + 1 (the word-length range allowed by the dictionary).

For each end index e (from 1 to m), we only test substrings whose lengths lie in [minWordLen, maxWordLen] and do not exceed the available prefix (≤ e). Hence the number of candidates per step is at most min(rangeLen, e), and thus ≤ min(rangeLen, m) overall.

If checking one candidate requires reading/building the substring of length L (cost Θ(L)), then in the worst case L ≤ min(maxWordLen, m). Therefore, the total worst-case time complexity is: O(m × min(rangeLen, m) × min(maxWordLen, m)).

Each dictionary membership check is O(1) on average thanks to the hash set.

Space Complexity

The dynamic programming array dp stores one boolean for each prefix of the string, giving a space cost of O(m), where m = s.length.

The dictionary is stored in a hash set (wordSet), requiring O(n × avgWordLen) space overall, where n is the number of words and avgWordLen is the average word length in the dictionary. This includes both the set structure and the stored word strings.

Hence, the overall auxiliary space complexity is: O(m + n × avgWordLen).

Input-1

Word Break - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Approach (Dynamic Programming — End-Exclusive Prefixes with Length Bounds Optimization)

Initialization

Iteration Logic

Final Result

Time Complexity

Space Complexity