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.

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 can be reversed to form a word in wordDict

B. If s contains any substring that is not in wordDict

C. If s is exactly equal to one of the words in wordDict

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

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify what is being checked

   It is not about substrings not in the dictionary or exact matches only, but about segmenting s fully into dictionary words.

3. Final Answer:

   If s can be segmented into a sequence of dictionary words -> Option D

4. Quick Check:

   Word Break = segment string into dictionary words [OK]

Hint: Check if string splits fully into dictionary words [OK]

Common Mistakes:

• Thinking it checks for partial substrings only
• Confusing exact match with segmentation
• Assuming reversed words are considered

2. Which of the following TypeScript function signatures correctly represents a function solving the Word Break Problem?

easy

A. function wordBreak(words: string[], s: string): number

B. function wordBreak(s: string, wordDict: string[]): boolean

C. function wordBreak(s: number, wordDict: string): string

D. function wordBreak(s: string, wordDict: string): void

Solution

1. Step 1: Identify correct parameter types

   The function should take a string s and an array of strings wordDict representing the dictionary words.

2. Step 2: Identify correct return type

   The function returns a boolean indicating if s can be segmented or not.

3. Final Answer:

   function wordBreak(s: string, wordDict: string[]): boolean -> Option B

4. Quick Check:

   Correct params and boolean return [OK]

Hint: Function takes string and string array, returns boolean [OK]

Common Mistakes:

• Using wrong parameter types
• Returning wrong data type
• Swapping parameter order

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

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(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] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak("leetcode", ["leet", "code"]));

medium

A. SyntaxError

B. false

C. true

D. undefined

Solution

1. Step 1: Understand the dynamic programming approach

   The code uses a boolean array dp where dp[i] is true if substring s[0..i-1] can be segmented into dictionary words.

2. Step 2: Trace the example input "leetcode"

   "leet" and "code" are in the dictionary. The code finds "leet" at start and sets dp[4] true, then "code" from index 4 to 8 sets dp[8] true. So final dp[s.length] is true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   DP finds full segmentation = true [OK]

Hint: Check dp array for full string length true [OK]

Common Mistakes:

• Confusing substring indices
• Not breaking inner loop after true
• Misunderstanding dp array meaning

4. Identify the bug in this TypeScript code for the Word Break Problem:

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(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] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

medium

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

B. wordSet should be an array, not a Set

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

D. dp[0] should be false initially

Solution

1. Step 1: Check dp array initialization

   The dp array is created with size s.length, but it needs to be s.length + 1 to include the base case dp[0].

2. Step 2: Understand consequences of wrong dp size

   Accessing dp[s.length] will be out of bounds, causing runtime errors or incorrect results.

3. Final Answer:

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

4. Quick Check:

   dp size must cover 0 to s.length indices [OK]

Hint: dp array length = string length + 1 [OK]

Common Mistakes:

• Using dp array of wrong size
• Confusing Set with array for dictionary
• Incorrect substring index order

5. Given the string s = "applepenapplepenapple" and dictionary wordDict = ["apple", "pen"], what is the minimum number of segments needed to fully segment s into dictionary words?

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Break down the string into dictionary words

   The string is "applepenapplepenapple". The dictionary words are "apple" and "pen". The string can be segmented as "apple" + "pen" + "apple" + "pen" + "apple".

2. Step 2: Count the segments

   There are 5 segments total: apple, pen, apple, pen, apple.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Count dictionary words in segmentation = 5 [OK]

Hint: Count dictionary words in full segmentation [OK]

Common Mistakes:

• Counting characters instead of words
• Missing repeated segments
• Assuming fewer segments possible