Word Break Problem in DSA Typescript - Execution Trace

Concept Flow - Word Break Problem

Start with input string

↓

Check prefixes in dictionary

↓

If prefix found

↓

Mark prefix end

↓

Recursively check suffix

↓

If suffix breaks fully

↓

Return True

↓

If no prefix leads to full break

↓

Return False

The algorithm tries to split the string into dictionary words by checking prefixes and recursively verifying suffixes until the whole string is segmented or no valid segmentation is found.

Execution Sample

DSA Typescript

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];
}

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

Execution Table

Step	Operation	Substring Checked	dp Array State	Action	Result
0	Initialize dp	-	[true, false, false, false, false, false, false, false, false]	Set dp[0] = true	-
1	Check substrings ending at i=1	s[0:1] = 'l'	[true, false, false, false, false, false, false, false, false]	dp[0] is true and 'l' in dict? No	dp[1] = false
2	Check substrings ending at i=2	s[0:2] = 'le', s[1:2] = 'e'	[true, false, false, false, false, false, false, false, false]	No valid prefix found	dp[2] = false
3	Check substrings ending at i=3	s[0:3] = 'lee', s[1:3] = 'ee', s[2:3] = 'e'	[true, false, false, false, false, false, false, false, false]	No valid prefix found	dp[3] = false
4	Check substrings ending at i=4	s[0:4] = 'leet', s[1:4] = 'eet', s[2:4] = 'et', s[3:4] = 't'	[true, false, false, false, true, false, false, false, false]	'leet' in dict and dp[0] true	dp[4] = true
5	Check substrings ending at i=5	s[0:5] = 'leetc', s[1:5] = 'eetc', s[2:5] = 'etc', s[3:5] = 'tc', s[4:5] = 'c'	[true, false, false, false, true, false, false, false, false]	No valid prefix found	dp[5] = false
6	Check substrings ending at i=6	s[0:6] = 'leetco', s[1:6] = 'eetco', s[2:6] = 'etco', s[3:6] = 'tco', s[4:6] = 'co', s[5:6] = 'o'	[true, false, false, false, true, false, false, false, false]	No valid prefix found	dp[6] = false
7	Check substrings ending at i=7	s[0:7] = 'leetcod', s[1:7] = 'eetcod', s[2:7] = 'etcod', s[3:7] = 'tcod', s[4:7] = 'cod', s[5:7] = 'od', s[6:7] = 'd'	[true, false, false, false, true, false, false, false, false]	No valid prefix found	dp[7] = false
8	Check substrings ending at i=8	s[0:8] = 'leetcode', s[1:8] = 'eetcode', s[2:8] = 'etcode', s[3:8] = 'tcode', s[4:8] = 'code', s[5:8] = 'ode', s[6:8] = 'de', s[7:8] = 'e'	[true, false, false, false, true, false, false, false, true]	'code' in dict and dp[4] true	dp[8] = true

💡 Reached end of string with dp[s.length] = true, meaning string can be segmented.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
dp	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, false, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, false]	[true, false, false, false, true, false, false, false, true]
i	0	1	2	3	4	5	6	7	8
j	-	0 to 0	0 to 1	0 to 2	0 to 3	0 to 4	0 to 5	0 to 6	0 to 7

Key Moments - 3 Insights

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

dp[0] = true means an empty string can be segmented. This is the base case allowing the algorithm to check prefixes starting from the beginning, as seen in step 0 of the execution_table.

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

Once dp[i] is true, it means the substring up to i can be segmented, so no need to check further prefixes. This optimization is shown in step 4 and step 8 where the loop breaks early.

What does dp[i] = true represent?

dp[i] = true means the substring s[0:i] can be segmented into dictionary words. For example, dp[4] = true means 'leet' can be segmented, as shown in step 4.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the value of dp[4] after this step?

A undefined

B false

C true

D null

💡 Hint

Check the 'dp Array State' column at step 4 in the execution_table.

At which step does the dp array first get a true value besides dp[0]?

A Step 4

B Step 8

C Step 1

D Step 2

💡 Hint

Look at the 'dp Array State' column and find when a new true appears after dp[0].

If the word 'code' was not in the dictionary, what would be the value of dp[8] at the end?

A true

B false

C undefined

D null

💡 Hint

Refer to the last row in execution_table where dp[8] becomes true because 'code' is found.

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 where dp[j] is true and s[j:i] in dict
- Return dp[s.length] at end
- Efficiently checks all prefix splits

Full Transcript

The Word Break Problem checks if a string can be split into valid dictionary words. We use a dynamic programming array dp where dp[i] means the substring up to i can be segmented. We start with dp[0] = true for the empty string. For each position i, we check all previous positions j where dp[j] is true and if the substring from j to i is in the dictionary. If yes, dp[i] becomes true. We continue until the end of the string. If dp[s.length] is true, the string can be segmented. The execution table shows each step checking substrings and updating dp. Key moments clarify why dp[0] is true, why we break early, and what dp[i] means. The quiz tests understanding of dp updates and dictionary role.

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