Word Break Problem in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the string can be segmented by dictionary words.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

A0

Bi

Cs.length

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using j instead of i causes checking empty or wrong substring.

Using s.length causes out of range substring.

The substring end index should be 'i' to check the segment from j to i.

2fill in blank

medium

Complete the code to initialize the dp array correctly.

DSA Typescript

function wordBreak(s: string, wordDict: string[]): boolean {
  const dp: boolean[] = Array([1]).fill(false);
  dp[0] = true;
  // rest of the code
}

Drag options to blanks, or click blank then click option'

As.length + 1

BwordDict.length

Cs.length

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using s.length causes index out of range errors.

Using wordDict.length is unrelated to dp size.

dp array size should be s.length + 1 to include empty substring at dp[0].

3fill in blank

hard

Fix the error in the loop condition to avoid infinite loops.

DSA Typescript

for (let i = 1; [1]; i++) {
  for (let j = 0; j < i; j++) {
    // code
  }
}

Drag options to blanks, or click blank then click option'

Ai <= s.length

Bi < s.length

Ci >= s.length

Di > s.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using i < s.length causes missing last substring checks.

Using i >= s.length or i > s.length causes infinite or no loops.

The outer loop must run until i <= s.length to cover full string length.

4fill in blank

hard

Fill both blanks to correctly check substring and update dp array.

DSA Typescript

if (dp[[1]] && wordDict.includes(s.substring([2], i))) {
  dp[i] = true;
  break;
}

Drag options to blanks, or click blank then click option'

Aj

Bi

C0

Ds.length

Attempts:

3 left

💡 Hint

Common Mistakes

Using i in dp or substring start causes wrong checks.

Using 0 or s.length causes incorrect substring ranges.

Both blanks should be 'j' to check substring from j to i and dp[j].

5fill in blank

hard

Fill all three blanks to complete the word break function correctly.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

As.length + 1

B<=

Cj

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp size as s.length causes index errors.

Using i < s.length misses last character.

Using dp[i] instead of dp[j] causes logic errors.

dp size is s.length+1, loop runs while i <= s.length, and dp[j] checks previous valid segment.

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