Word Break Problem in DSA Javascript

Mental Model

We want to check if a long word can be split into smaller words from a list. We try breaking it step by step and see if all parts match.

Analogy: Imagine you have a long sentence without spaces, and a dictionary of known words. You try to put spaces in the sentence so every piece is a real word from the dictionary.

word: w o r d b r e a k
      ↑ start here
words: [word, break, problem]
We try to split word into known words step by step.

Dry Run Walkthrough

Input: string: 'wordbreak', dictionary: ['word', 'break', 'problem']

Goal: Check if 'wordbreak' can be split into words from the dictionary

Step 1: Check prefix 'w', not in dictionary

'w' (no match)

Why: Try smallest prefix to find a dictionary word

Step 2: Check prefix 'wo', not in dictionary

'wo' (no match)

Why: Try longer prefix to find a dictionary word

Step 3: Check prefix 'wor', not in dictionary

'wor' (no match)

Why: Try longer prefix to find a dictionary word

Step 4: Check prefix 'word', found in dictionary

'word' (match found)

Why: Found a valid word, now check remaining 'break'

Step 5: Recursively check 'break' with dictionary

'break' to check

Why: Split problem into smaller substring

Step 6: Check prefix 'b', not in dictionary

'b' (no match)

Why: Try smallest prefix of 'break'

Step 7: Check prefix 'br', not in dictionary

'br' (no match)

Why: Try longer prefix

Step 8: Check prefix 'bre', not in dictionary

'bre' (no match)

Why: Try longer prefix

Step 9: Check prefix 'brea', not in dictionary

'brea' (no match)

Why: Try longer prefix

Step 10: Check prefix 'break', found in dictionary

'break' (match found)

Why: Found valid word, no remaining string left

Result:

'word' -> 'break' -> null
Answer: true (can split)

Annotated Code

DSA Javascript

class WordBreak {
  constructor(dictionary) {
    this.dictionary = new Set(dictionary);
    this.memo = {};
  }

  canBreak(s) {
    if (s.length === 0) return true; // empty string means success
    if (s in this.memo) return this.memo[s]; // return cached result

    for (let i = 1; i <= s.length; i++) {
      const prefix = s.slice(0, i);
      if (this.dictionary.has(prefix)) {
        // check if rest can be broken
        if (this.canBreak(s.slice(i))) {
          this.memo[s] = true; // cache true
          return true;
        }
      }
    }

    this.memo[s] = false; // cache false
    return false;
  }
}

// Driver code
const dictionary = ['word', 'break', 'problem'];
const wb = new WordBreak(dictionary);
const input = 'wordbreak';
const result = wb.canBreak(input);
console.log(result);

if (s.length === 0) return true; // empty string means success

base case: empty string means all parts matched

if (s in this.memo) return this.memo[s]; // return cached result

use memo to avoid repeated work

for (let i = 1; i <= s.length; i++) {

try all prefixes from length 1 to full string

const prefix = s.slice(0, i);

extract current prefix to check

if (this.dictionary.has(prefix)) {

check if prefix is a valid word

if (this.canBreak(s.slice(i))) {

recursively check remaining substring

this.memo[s] = true; // cache true return true;

cache and return true if rest can be broken

this.memo[s] = false; // cache false return false;

cache and return false if no prefix works

Output

true

Complexity Analysis

Time: O(n^2) because for each substring we try all prefixes and recursion with memo avoids repeated work

Space: O(n) for recursion stack and memoization storage for substrings

vs Alternative: Naive recursion without memo is exponential due to repeated substring checks; memoization reduces it to polynomial time

Edge Cases

empty string input

returns true immediately because empty string means successful split

DSA Javascript

if (s.length === 0) return true; // empty string means success

string with no matching dictionary words

returns false after checking all prefixes

DSA Javascript

this.memo[s] = false; // cache false
return false;

dictionary contains single character words

works correctly by checking all prefixes including single characters

DSA Javascript

for (let i = 1; i <= s.length; i++) {

When to Use This Pattern

When you see a problem asking if a string can be split into valid dictionary words, use the Word Break pattern with recursion and memoization to efficiently check all splits.

Common Mistakes

Mistake: Not using memoization causing exponential time and timeout
Fix: Add a memo object to store results of substrings already checked

Mistake: Checking prefixes incorrectly by off-by-one slicing
Fix: Use slice(0, i) with i from 1 to s.length inclusive to get all prefixes

Summary

Checks if a string can be split into valid words from a dictionary.

Use when you need to verify if a string can be segmented into dictionary words.

Try all prefixes and use recursion with memoization to avoid repeated work.

Practice

1. What does the Word Break Problem ask you to determine about a given string s and a dictionary of words wordDict?

easy

A. If s contains any substring from wordDict

B. If s can be segmented into a space-separated sequence of one or more dictionary words

C. If s is exactly equal to any word in wordDict

D. If s can be reversed to form a word in wordDict

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks whether the entire string s can be split into parts where each part is a word from the dictionary wordDict.

2. Step 2: Compare options with the problem definition

   If s can be segmented into a space-separated sequence of one or more dictionary words correctly states the problem as checking if s can be segmented into dictionary words. Other options describe partial or different checks.

3. Final Answer:

   If s can be segmented into a space-separated sequence of one or more dictionary words -> Option B

4. Quick Check:

   Word Break Problem = segmentation check [OK]

Hint: Remember: Word Break means full segmentation check [OK]

Common Mistakes:

• Thinking it checks for substring presence only
• Confusing exact match with segmentation
• Assuming reversal or partial matches

2. Which of the following is the correct way to declare a function named wordBreak in JavaScript that takes two parameters: s (string) and wordDict (array)?

easy

A. function wordBreak[s, wordDict] {}

B. def wordBreak(s, wordDict): {}

C. func wordBreak(s, wordDict) {}

D. function wordBreak(s, wordDict) {}

Solution

1. Step 1: Recall JavaScript function syntax

   In JavaScript, functions are declared using the function keyword followed by the name and parentheses enclosing parameters.

2. Step 2: Check each option's syntax

   function wordBreak(s, wordDict) {} uses correct JavaScript syntax. def wordBreak(s, wordDict): {} is Python syntax. func wordBreak(s, wordDict) {} resembles Go syntax. function wordBreak[s, wordDict] {} uses incorrect brackets.

3. Final Answer:

   function wordBreak(s, wordDict) {} -> Option D

4. Quick Check:

   JS function syntax = function name(params) {} [OK]

Hint: JS functions use parentheses for parameters, not brackets [OK]

Common Mistakes:

• Using Python or other language syntax
• Using square brackets instead of parentheses
• Missing function keyword

3. What will be the output of the following JavaScript code?

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

function wordBreak(s, wordDict) {
  const dp = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak(s, wordDict));

medium

A. undefined

B. false

C. true

D. TypeError

Solution

1. Step 1: Understand the dynamic programming array dp

   dp[i] means if substring s[0..i-1] can be segmented. dp[0] = true means empty string is segmentable.

2. Step 2: Trace the loops and substring checks

   For s = "leetcode", wordDict = ["leet", "code"], dp updates to true at dp[4] ("leet") and dp[8] ("leetcode") because both substrings are in wordDict.

3. Final Answer:

   true -> Option C

4. Quick Check:

   "leetcode" split as "leet" + "code" = true [OK]

Hint: Check dp array updates for substring matches [OK]

Common Mistakes:

• Confusing substring indices
• Not initializing dp[0] to true
• Assuming partial matches are enough

4. The following code attempts to solve the Word Break Problem but has a bug. What is the bug?

function wordBreak(s, wordDict) {
  const dp = Array(s.length).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordDict.includes(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

medium

A. dp array length is incorrect; should be s.length + 1

B. dp[0] should be false, not true

C. substring indices are reversed in s.substring(j, i)

D. wordDict.includes should be replaced with wordDict.indexOf

Solution

1. Step 1: Check dp array initialization

   dp array length should be s.length + 1 to include dp[s.length] index. Current length s.length causes out-of-bound errors.

2. Step 2: Verify dp usage and return statement

   dp[s.length] is accessed at return, but dp array does not have that index, causing undefined or error.

3. Final Answer:

   dp array length is incorrect; should be s.length + 1 -> Option A

4. Quick Check:

   dp length = s.length + 1 for full coverage [OK]

Hint: dp array must cover from 0 to s.length inclusive [OK]

Common Mistakes:

• Using dp length equal to s.length only
• Misunderstanding dp index meaning
• Ignoring off-by-one errors

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm will allow it to return true only if all possible segmentations of s are valid dictionary words (not just one)?

hard

A. Change dp to store counts of valid segmentations and check if count equals total segmentations

B. Return true as soon as one valid segmentation is found (current approach)

C. Use a stack to store all substrings and check each against wordDict once

D. Sort wordDict and use binary search for substring checks

Solution

1. Step 1: Understand current algorithm behavior

   The current algorithm returns true if at least one segmentation exists. It does not check all segmentations.

2. Step 2: Modify dp to count all valid segmentations

   By storing counts of valid segmentations at each dp index, we can compare total segmentations to valid ones. Returning true only if all segmentations are valid requires counting and comparing.

3. Final Answer:

   Change dp to store counts of valid segmentations and check if count equals total segmentations -> Option A

4. Quick Check:

   Counting all segmentations ensures all are valid [OK]

Hint: Count all segmentations, not just existence, for full validation [OK]

Common Mistakes:

• Assuming one valid segmentation means all are valid
• Ignoring need to track all segmentation paths
• Confusing substring search optimization with segmentation count