Word Break Problem in DSA Javascript - Execution Trace

Concept Flow - Word Break Problem

Start with input string

↓

Check prefixes in dictionary

↓

If prefix found

↓

Mark prefix end

↓

Recursively check remaining string

↓

If full string segmented

↓

Return True

↓

Else return False

The flow tries to split the string into dictionary words by checking prefixes and recursively verifying the rest.

Execution Sample

DSA Javascript

const 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.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
};

This code checks if the string can be segmented into dictionary words using dynamic programming.

Execution Table

Step	Operation	Index i	Index j	Substring s[j:i]	dp Array State	Action
1	Initialize dp	-	-	-	[true, false, false, false, false, false]	Set dp[0] = true
2	i=1, j=0	1	0	"c"	[true, false, false, false, false, false]	No match, dp[1] remains false
3	i=2, j=0	2	0	"ca"	[true, false, false, false, false, false]	No match, dp[2] remains false
4	i=2, j=1	2	1	"a"	[true, false, false, false, false, false]	No match, dp[2] remains false
5	i=3, j=0	3	0	"cat"	[true, false, false, true, false, false]	Match found, dp[3] = true
6	i=4, j=0	4	0	"cats"	[true, false, false, true, false, false]	No match, dp[4] remains false
7	i=4, j=3	4	3	"s"	[true, false, false, true, true, false]	Match found, dp[4] = true
8	i=5, j=0	5	0	"catsa"	[true, false, false, true, true, false]	No match, dp[5] remains false
9	i=5, j=4	5	4	"a"	[true, false, false, true, true, false]	No match, dp[5] remains false
10	i=5, j=3	5	3	"sa"	[true, false, false, true, true, false]	No match, dp[5] remains false
11	i=5, j=2	5	2	"tsa"	[true, false, false, true, true, false]	No match, dp[5] remains false
12	i=5, j=1	5	1	"atsa"	[true, false, false, true, true, false]	No match, dp[5] remains false
13	i=5, j=0	5	0	"catsa"	[true, false, false, true, true, false]	No match, dp[5] remains false
14	End	-	-	-	[true, false, false, true, true, false]	dp[s.length] is false, return false

💡 Reached end of string; dp[s.length] is false meaning string cannot be segmented fully

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 7	After Step 14
dp	[false, false, false, false, false, false]	[true, false, false, false, false, false]	[true, false, false, true, false, false]	[true, false, false, true, true, false]	[true, false, false, true, true, false]
i	0	1	3	4	5
j	-	0	0	3	-

Key Moments - 3 Insights

Why do we set dp[0] = true at the start?

dp[0] = true means an empty string can always be segmented, which is the base case for building up solutions (see Step 1 in execution_table).

Why do we break the inner loop when dp[i] becomes true?

Once dp[i] is true, it means the substring s[0:i] can be segmented, so no need to check further prefixes (see Step 5).

Why does dp[s.length] being false mean the string can't be segmented?

dp[s.length] represents if the whole string can be segmented; false means no valid segmentation was found (see Step 14).

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the substring s[j:i] checked?

A "ca"

B "cat"

C "a"

D "cats"

💡 Hint

Check the 'Substring s[j:i]' column at Step 5 in execution_table.

At which step does dp[4] become true?

A Step 5

B Step 6

C Step 7

D Step 14

💡 Hint

Look at the 'dp Array State' column and 'Action' at Steps 6 and 7.

If the wordDict included "a", how would dp[5] change by Step 14?

A dp[5] would be true

B dp[5] would remain false

C dp[5] would be undefined

D dp[5] would be null

💡 Hint

Check how dp[i] updates when substring matches dictionary words in execution_table.

Concept Snapshot

Word Break Problem:
- Use dp array of length s+1, dp[0]=true
- dp[i] = true if s[0:i] can be segmented
- For each i, check all j < i
- If dp[j] true and s[j:i] in dict, dp[i]=true
- Return dp[s.length] at end

Full Transcript

The Word Break Problem checks if a string can be split into dictionary words. We use a dp array where dp[i] means the substring up to i can be segmented. Start with dp[0] true for empty string. For each position i, check all prefixes ending at i. If a prefix is in the dictionary and the substring before it can be segmented (dp[j] true), mark dp[i] true. If dp at the full string length is true, the string can be segmented. Otherwise, it cannot. This approach uses dynamic programming to avoid repeated checks.

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