Word Break Problem in DSA C - Execution Trace

Concept Flow - Word Break Problem

Start with input string

↓

Initialize DP array with False

↓

Set dp[0

↓

For each position i in string

↓

For each position j < i

↓

Check if dp[j

Yes No↓

Set dp[i

↓

Repeat until end of string

↓

Return dp[string_length

This flow shows how we use a DP array to check if substrings can be formed from dictionary words step-by-step.

Execution Sample

DSA C

bool wordBreak(char* s, char** wordDict, int wordDictSize) {
  int n = strlen(s);
  bool dp[n+1];
  dp[0] = true;
  for (int i = 1; i <= n; i++) {
    dp[i] = false;
    for (int j = 0; j < i; j++) {
      if (dp[j] && substring_in_dict(s, j, i, wordDict, wordDictSize)) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}

This code checks if the string s can be segmented into dictionary words using a DP array.

Execution Table

Step	Operation	Substring Checked	dp Array State	Action	Visual State
1	Initialize dp	N/A	[True, False, False, False, False, False, False]	Set dp[0] = True	dp: T F F F F F F
2	i=1, j=0	s[0:1] = 'c'	[True, False, False, False, False, False, False]	Check if 'c' in dict and dp[0] True	No match, dp[1] stays False
3	i=2, j=0	s[0:2] = 'ca'	[True, False, False, False, False, False, False]	No match, dp[2] stays False	dp: T F F F F F F
4	i=2, j=1	s[1:2] = 'a'	[True, False, False, False, False, False, False]	No match, dp[2] stays False	dp: T F F F F F F
5	i=3, j=0	s[0:3] = 'cat'	[True, False, False, True, False, False, False]	Match found, dp[3] = True	dp: T F F T F F F
6	i=4, j=0	s[0:4] = 'cats'	[True, False, False, True, False, False, False]	No match, dp[4] stays False	dp: T F F T F F F
7	i=4, j=3	s[3:4] = 's'	[True, False, False, True, True, False, False]	Match found, dp[4] = True	dp: T F F T T F F
8	i=5, j=0	s[0:5] = 'catsd'	[True, False, False, True, True, False, False]	No match, dp[5] stays False	dp: T F F T T F F
9	i=5, j=4	s[4:5] = 'd'	[True, False, False, True, True, False, False]	No match, dp[5] stays False	dp: T F F T T F F
10	i=6, j=0	s[0:6] = 'catsdo'	[True, False, False, True, True, False, False]	No match, dp[6] stays False	dp: T F F T T F F
11	i=6, j=5	s[5:6] = 'o'	[True, False, False, True, True, False, False]	No match, dp[6] stays False	dp: T F F T T F F
12	i=7, j=0	s[0:7] = 'catsdog'	[True, False, False, True, True, False, False]	No match, dp[7] stays False	dp: T F F T T F F
13	i=7, j=4	s[4:7] = 'dog'	[True, False, False, True, True, False, True]	Match found, dp[7] = True	dp: T F F T T F T
14	End	N/A	[True, False, False, True, True, False, True]	Return dp[n] = True	Final dp: T F F T T F T

💡 Reached end of string; dp[n] = True means string can be segmented.

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 7	After Step 13	Final
dp	[False, False, False, False, False, False, False, False]	[True, False, False, False, False, False, False, False]	[True, False, False, True, False, False, False, False]	[True, False, False, True, True, False, False, False]	[True, False, False, True, True, False, False, True]	[True, False, False, True, True, False, False, True]
i	0	1	3	4	7	7
j	0	0	0	3	4	4

Key Moments - 3 Insights

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

dp[0] represents the empty string, which is always 'breakable'. This allows checking substrings starting at index 0, as seen in step 1 of the execution_table.

Why do we break the inner loop when 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 j values. This is shown in step 5 where dp[3] is set True and loop breaks.

Why does dp array have length n+1?

dp[i] represents substring s[0:i], so dp[n] covers the full string. This is why dp array size is n+1, as shown in variable_tracker and execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the dp array state?

A [True, False, False, True, False, False]

B [True, False, False, True, False, False, False]

C [True, False, False, True, True, False, False]

D [True, False, False, False, False, False, False]

💡 Hint

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

At which step does dp[4] become True?

A Step 7

B Step 6

C Step 5

D Step 4

💡 Hint

Look at the 'Action' and 'dp Array State' columns for dp[4] in execution_table.

If the substring 'dog' was not in the dictionary, what would be the final dp[n] value?

A True

B Depends on dp[0]

C False

D True only if dp[3] is True

💡 Hint

Refer to step 13 where dp[7] is set True because 'dog' is found; without it dp[7] stays False.

Concept Snapshot

Word Break Problem:
- Use dp array of size n+1, dp[0] = True
- dp[i] = True if substring s[0:i] can be segmented
- For each i, check all j < i: if dp[j] True and s[j:i] in dict
- Return dp[n] as final answer
- Break inner loop early when dp[i] becomes True

Full Transcript

The Word Break Problem checks if a string can be split into dictionary words. We use a boolean dp array 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. If dp[j] is True and the substring from j to i is in the dictionary, we set dp[i] to True and stop checking further j. At the end, dp[n] tells if the whole string can be segmented. The execution table shows each step with substring checks and dp array updates. Key moments clarify why dp[0] is True, why we break early, and why dp size is n+1. The quiz tests understanding of dp states and final results.