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.

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 is a palindrome

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if the entire string s can be split into parts where each part is a word in the dictionary.

2. Step 2: Compare options with the problem

   If s can be segmented into a space-separated sequence of one or more dictionary words correctly describes this segmentation into dictionary words. Other options describe 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 into dictionary words [OK]

Common Mistakes:

• Thinking it checks for substring presence only
• Confusing exact match with segmentation
• Assuming palindrome check

2. Which of the following C code snippets correctly declares a function prototype for solving the Word Break Problem?

easy

A. int wordBreak(char s[], char *wordDict[], int wordDictSize);

B. void wordBreak(char s[], char wordDict[], int size);

C. int wordBreak(char *s, char *wordDict, int wordDictSize);

D. int wordBreak(char **s, char **wordDict, int wordDictSize);

Solution

1. Step 1: Understand parameter types for the Word Break function

   The string s is a character array, so char s[] or char *s works. The dictionary is an array of strings, so char *wordDict[] is correct. The size is an integer.

2. Step 2: Check each option

   int wordBreak(char s[], char *wordDict[], int wordDictSize); matches the correct signature: int wordBreak(char s[], char *wordDict[], int wordDictSize); int wordBreak(char *s, char *wordDict, int wordDictSize); uses char *wordDict which is incorrect for array of strings. void wordBreak(char s[], char wordDict[], int size); uses char wordDict[] which is incorrect for array of strings. int wordBreak(char **s, char **wordDict, int wordDictSize); uses char **s which is incorrect for a single string.

3. Final Answer:

   int wordBreak(char s[], char *wordDict[], int wordDictSize); -> Option A

4. Quick Check:

   Function prototype with string and array of strings = int wordBreak(char s[], char *wordDict[], int wordDictSize); [OK]

Hint: Dictionary is array of strings: use char *wordDict[] [OK]

Common Mistakes:

• Using char wordDict[] instead of array of strings
• Using char **s for input string
• Wrong return type or missing parameters

3. What will be the output of the following C code snippet for the Word Break Problem?

char *dict[] = {"leet", "code"};
int result = wordBreak("leetcode", dict, 2);
printf("%d", result);

Assuming wordBreak returns 1 if segmentation is possible, else 0.

medium

A. 1

B. 0

C. Compilation error

D. Runtime error

Solution

1. Step 1: Analyze the input string and dictionary

   The string is "leetcode" and dictionary contains "leet" and "code".

2. Step 2: Check if string can be segmented

   "leetcode" can be split as "leet" + "code", both in dictionary, so segmentation is possible.

3. Final Answer:

   1 -> Option A

4. Quick Check:

   "leetcode" segmented as "leet" + "code" = 1 [OK]

Hint: Check if string splits fully into dictionary words [OK]

Common Mistakes:

• Assuming partial match is enough
• Confusing return values
• Ignoring dictionary contents

4. Identify the error in the following C code snippet for the Word Break Problem:

int wordBreak(char *s, char **wordDict, int wordDictSize) {
    int len = strlen(s);
    int dp[len+1];
    dp[0] = 1;
    for (int i = 1; i <= len; i++) {
        dp[i] = 0;
        for (int j = 0; j < i; j++) {
            if (dp[j] && strncmp(s+j, wordDict[i], i-j) == 0) {
                dp[i] = 1;
                break;
            }
        }
    }
    return dp[len];
}

medium

A. Missing return statement

B. dp array not initialized properly

C. Using wordDict[i] instead of wordDict[j] in strncmp

D. Loop indices are out of range

Solution

1. Step 1: Understand the nested loop and string comparison

   The inner loop checks substrings from index j to i. It should compare with wordDict[j], not wordDict[i].

2. Step 2: Identify the incorrect array index usage

   Using wordDict[i] is wrong because i goes up to length of s, which may exceed wordDictSize and is unrelated to dictionary indexing.

3. Final Answer:

   Using wordDict[i] instead of wordDict[j] in strncmp -> Option C

4. Quick Check:

   Index in dictionary should match substring start index [OK]

Hint: Check indices used for dictionary access in loops [OK]

Common Mistakes:

• Mixing loop variables for dictionary access
• Not initializing dp array correctly
• Ignoring return statement

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which approach correctly solves the Word Break Problem using dynamic programming in C?

hard

A. Use recursion without memoization to check all substring splits

B. Use a stack to store all dictionary words and pop when matched

C. Sort the dictionary and check if s starts with any word

D. Use a boolean dp array where dp[i] is true if s[0..i-1] can be segmented, then check all substrings ending at i

Solution

1. Step 1: Understand dynamic programming approach

   We create a boolean dp array where dp[i] is true if substring s[0..i-1] can be segmented into dictionary words.

2. Step 2: Check all substrings ending at each position

   For each position i, check all j < i where dp[j] is true and substring s[j..i-1] is in dictionary. If yes, set dp[i] true.

3. Step 3: Return dp[length of s]

   If dp at the end is true, the string can be segmented.

4. Final Answer:

   Use a boolean dp array where dp[i] is true if s[0..i-1] can be segmented, then check all substrings ending at i -> Option D

5. Quick Check:

   DP boolean array with substring checks = Use a boolean dp array where dp[i] is true if s[0..i-1] can be segmented, then check all substrings ending at i [OK]

Hint: Use dp array to track segmentation up to each index [OK]

Common Mistakes:

• Using recursion without memo causing timeout
• Sorting dictionary does not help segmentation
• Stack approach is incorrect for this problem