Word Break Problem in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the string is empty at the start of the recursion.

DSA Javascript

function wordBreak(s, wordDict) {
  if (s.length [1] 0) return true;
  // rest of the code
}

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

A=

B==

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using assignment '=' instead of comparison '=='

Using greater than or less than operators incorrectly

We check if the string length is equal to zero to know if we have successfully segmented the entire string.

2fill in blank

medium

Complete the code to iterate over the string prefixes.

DSA Javascript

for (let i = 1; i <= s.length; i++) {
  let prefix = s.slice(0, [1]);
  // rest of the code
}

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

Ai

Bs.length

C0

Di + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as slice end index which results in empty string

Using s.length which slices the entire string

We slice the string from 0 to i to get the prefix for each iteration.

3fill in blank

hard

Fix the error in checking if the prefix is in the dictionary.

DSA Javascript

if (wordDict.[1](prefix)) {
  if (wordBreak(s.slice(i), wordDict)) {
    return true;
  }
}

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

AindexOf

Bcontains

Chas

Dincludes

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'contains' which is not a JavaScript array method

Using 'has' which is for Sets

Using 'indexOf' without comparison

In JavaScript arrays, 'includes' checks if an element exists in the array.

4fill in blank

hard

Fill both blanks to complete the memoization check and store.

DSA Javascript

function wordBreakMemo(s, wordDict, memo = {}) {
  if (s in [1]) return [2][s];
  // rest of the code
}

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

Amemo

BwordDict

Cs

Dthis

Attempts:

3 left

💡 Hint

Common Mistakes

Checking in wordDict instead of memo

Using 'this' or 's' incorrectly

We check if the string is already in the memo object and return the stored result to avoid repeated work.

5fill in blank

hard

Fill all three blanks to store the result in memo and return it.

DSA Javascript

memo[s] = [1];
return [2][[3]];

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

Afalse

Bmemo

Cs

Dtrue

Attempts:

3 left

💡 Hint

Common Mistakes

Returning false directly instead of from memo

Using wrong keys or variables

We store false in memo for the current string and then return memo[s].

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