Word Break Problem in DSA Typescript

Mental Model

We want to check if a sentence can be split into valid words from a dictionary. We try breaking the sentence at every position and see if the left part is a word and the right part can also be split similarly.

Analogy: Imagine you have a long chain of beads and a box of smaller bead groups. You want to see if you can break the long chain into smaller groups exactly matching the groups in the box.

sentence: w o r d b r e a k
dictionary: [word, break, problem]

Check splits:
word | breakproblem
wordbreak | problem
wordbreakproblem

Try to find valid splits step by step.

Dry Run Walkthrough

Input: sentence: 'wordbreak', dictionary: ['word', 'break']

Goal: Determine if 'wordbreak' can be segmented into dictionary words

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

No valid split at prefix 'w'

Why: We start checking from the smallest prefix to find a valid word

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

No valid split at prefix 'wo'

Why: Continue checking longer prefixes

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

No valid split at prefix 'wor'

Why: Still no valid word found

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

'word' is valid, now check suffix 'break'

Why: Found a valid word, now check if the rest can be segmented

Step 5: Check suffix 'break' similarly

'break' is in dictionary

Why: Suffix is also a valid word, so whole string can be segmented

Result:

wordbreak -> segmented as 'word' + 'break' -> true

Annotated Code

DSA Typescript

class WordBreak {
  private dictionary: Set<string>;

  constructor(words: string[]) {
    this.dictionary = new Set(words);
  }

  canSegment(s: string): boolean {
    const n = s.length;
    const dp: boolean[] = Array(n + 1).fill(false);
    dp[0] = true; // empty string can always be segmented

    for (let i = 1; i <= n; i++) {
      for (let j = 0; j < i; j++) {
        if (dp[j] && this.dictionary.has(s.substring(j, i))) {
          dp[i] = true; // mark position i as reachable
          break; // no need to check further splits for i
        }
      }
    }
    return dp[n];
  }
}

// Driver code
const sentence = 'wordbreak';
const dict = ['word', 'break'];
const wb = new WordBreak(dict);
console.log(wb.canSegment(sentence) ? 'true' : 'false');

dp[0] = true; // empty string can always be segmented

Initialize base case: empty string is segmentable

for (let i = 1; i <= n; i++) {

Check all prefixes of the string

for (let j = 0; j < i; j++) {

Try all splits of prefix s[0..i-1]

if (dp[j] && this.dictionary.has(s.substring(j, i))) {

If left part is segmentable and right part is a dictionary word, mark dp[i]

dp[i] = true; // mark position i as reachable

Mark current prefix as segmentable

break; // no need to check further splits for i

Stop checking splits once dp[i] is true

return dp[n];

Return if whole string is segmentable

Output

true

Complexity Analysis

Time: O(n^2) because for each position we check all previous positions to find valid splits

Space: O(n) for the dp array storing segmentability up to each index

vs Alternative: Compared to a naive recursive approach which can be exponential, this dynamic programming approach is efficient and avoids repeated work

Edge Cases

empty string

returns true because empty string can be segmented trivially

DSA Typescript

dp[0] = true; // empty string can always be segmented

string with no valid segmentation

returns false because no dictionary words match any prefix

DSA Typescript

if (dp[j] && this.dictionary.has(s.substring(j, i))) { dp[i] = true; }

string equals a single dictionary word

returns true immediately after checking full string

DSA Typescript

if (dp[j] && this.dictionary.has(s.substring(j, i))) { dp[i] = true; }

When to Use This Pattern

When you need to check if a string can be split into valid dictionary words, use the Word Break pattern with dynamic programming to efficiently test all prefixes.

Common Mistakes

Mistake: Not initializing dp[0] to true, causing all checks to fail
Fix: Set dp[0] = true to represent empty string segmentation

Mistake: Not breaking inner loop after finding a valid split, causing unnecessary checks
Fix: Add break after dp[i] = true to optimize

Summary

Checks if a string can be split into dictionary words using dynamic programming.

Use when you want to verify if a sentence can be segmented into valid words.

The key insight is to build up solutions for prefixes and reuse them to avoid repeated work.