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.