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↓

Set dp[i

↓

Continue until end of string

↓

Return dp[string length

The flow shows how we use a boolean array to mark valid breaks in the string by checking all substrings against the dictionary.

Execution Sample

DSA C++

string s = "leetcode";
vector<string> dict = {"leet", "code"};
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); i++) {
  for (int j = 0; j < i; j++) {
    if (dp[j] && (find(dict.begin(), dict.end(), s.substr(j, i-j)) != dict.end())) {
      dp[i] = true;
      break;
    }
  }
}
return dp[s.size()];

This code checks if the string "leetcode" can be segmented into words from the dictionary {"leet", "code"} using dynamic programming.

Execution Table

Step	Operation	i	j	Substring Checked	dp Array State	Action
1	Initialize dp	-	-	-	[true, false, false, false, false, false, false, false, false]	Set dp[0] = true
2	Check substring	1	0	"l"	[true, false, false, false, false, false, false, false, false]	dp[0] true but "l" not in dict
3	Check substring	2	0	"le"	[true, false, false, false, false, false, false, false, false]	dp[0] true but "le" not in dict
4	Check substring	2	1	"e"	[true, false, false, false, false, false, false, false, false]	dp[1] false, skip
5	Check substring	3	0	"lee"	[true, false, false, false, false, false, false, false, false]	dp[0] true but "lee" not in dict
6	Check substring	3	1	"ee"	[true, false, false, false, false, false, false, false, false]	dp[1] false, skip
7	Check substring	3	2	"e"	[true, false, false, false, false, false, false, false, false]	dp[2] false, skip
8	Check substring	4	0	"leet"	[true, false, false, false, false, false, false, false, false]	dp[0] true and "leet" in dict, set dp[4] = true
9	Check substring	5	0	"leetc"	[true, false, false, false, true, false, false, false, false]	dp[0] true but "leetc" not in dict
10	Check substring	5	4	"c"	[true, false, false, false, true, false, false, false, false]	dp[4] true but "c" not in dict
11	Check substring	6	0	"leetco"	[true, false, false, false, true, false, false, false, false]	dp[0] true but "leetco" not in dict
12	Check substring	6	4	"co"	[true, false, false, false, true, false, false, false, false]	dp[4] true but "co" not in dict
13	Check substring	6	5	"o"	[true, false, false, false, true, false, false, false, false]	dp[5] false, skip
14	Check substring	7	0	"leetcod"	[true, false, false, false, true, false, false, false, false]	dp[0] true but "leetcod" not in dict
15	Check substring	7	4	"cod"	[true, false, false, false, true, false, false, false, false]	dp[4] true but "cod" not in dict
16	Check substring	7	5	"od"	[true, false, false, false, true, false, false, false, false]	dp[5] false, skip
17	Check substring	7	6	"d"	[true, false, false, false, true, false, false, false, false]	dp[6] false, skip
18	Check substring	8	0	"leetcode"	[true, false, false, false, true, false, false, false, false]	dp[0] true but "leetcode" not in dict
19	Check substring	8	4	"code"	[true, false, false, false, true, false, false, false, false]	dp[4] true and "code" in dict, set dp[8] = true
20	End	-	-	-	[true, false, false, false, true, false, false, false, true]	dp[8] true means string can be segmented

💡 Reached end of string with dp[s.size()] = true, so string can be segmented

Variable Tracker

Variable	Start	After Step 1	After Step 8	After Step 19	Final
dp	[false,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,true]	[true,false,false,false,true,false,false,false,true]
i	0	1	4	8	8
j	-	0	0	4	-

Key Moments - 3 Insights

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

dp[0] represents the empty string which is always segmentable. This is the base case allowing the algorithm to build up solutions for longer substrings, 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 optimization is shown in step 8 and step 19 where dp[i] is set and loop breaks.

What does dp[i] = true actually mean?

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

Visual Quiz - 3 Questions

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

A [true, true, false, false, false, false, false, false, false]

B [true, false, false, false, false, false, false, false, false]

C [true, false, false, false, true, false, false, false, false]

D [false, false, false, false, true, false, false, false, false]

💡 Hint

Check the dp Array State column in row with Step 8 in execution_table

At which step does the substring "code" get recognized as in the dictionary?

A Step 19

B Step 4

C Step 8

D Step 14

💡 Hint

Look for the substring "code" in the Substring Checked column and when dp[i] is set true

If the dictionary did not contain "leet", which dp index would fail to become true?

A dp[8]

B dp[4]

C dp[0]

D dp[1]

💡 Hint

dp[4] corresponds to substring "leet" as shown in execution_table step 8

Concept Snapshot

Word Break Problem:
- Use a boolean dp array of size s.length+1
- dp[0] = true (empty string base case)
- For each i, check all j < i
- If dp[j] is true and s[j:i] in dictionary, set dp[i] = true
- Result is dp[s.length()] indicating if full string can be segmented

Full Transcript

The Word Break Problem uses a dynamic programming approach to determine if a string can be segmented into dictionary words. We create a boolean 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 positions j before i. If dp[j] is true and the substring from j to i is in the dictionary, we set dp[i] to true. We continue until the end of the string. If dp at the string length is true, the string can be segmented. The example with "leetcode" and dictionary {"leet", "code"} shows dp[4] and dp[8] becoming true, confirming segmentation is possible.

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 is exactly equal to one of the words in wordDict

B. If s contains any substring from wordDict

C. If s can be segmented into a space-separated sequence of one or more dictionary words

D. If s is a palindrome formed by dictionary words

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 from the dictionary wordDict.

2. Step 2: Differentiate from similar concepts

   It is not enough for s to contain a dictionary word or be equal to one; the whole string must be fully segmented into dictionary words.

3. Final Answer:

   If s can be segmented into a sequence of dictionary words -> Option C

4. Quick Check:

   Word Break = Full segmentation check [OK]

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

Common Mistakes:

• Thinking partial substring match is enough
• Confusing exact match with segmentation
• Ignoring the order of words in segmentation

2. Which of the following is the correct C++ syntax to declare a function named wordBreak that takes a string s and a vector<string> named wordDict and returns a bool?

easy

A. bool wordBreak(string s, vector<string> &wordDict);

B. bool wordBreak(string s, vector<string>& wordDict);

C. bool wordBreak(string s, vector<string> wordDict);

D. bool wordBreak(string s, vector<string> wordDict&);

Solution

1. Step 1: Understand parameter passing in C++

   Passing vector<string> by reference requires the ampersand & after the type, with optional space before the variable name.

2. Step 2: Check syntax correctness

   bool wordBreak(string s, vector<string> &wordDict); correctly places the ampersand before the parameter name with a space: vector<string> &wordDict. bool wordBreak(string s, vector<string>& wordDict); is also valid but less common spacing. bool wordBreak(string s, vector<string> wordDict&); is invalid syntax.

3. Final Answer:

   bool wordBreak(string s, vector<string> &wordDict); -> Option A

4. Quick Check:

   Reference parameter syntax = bool wordBreak(string s, vector<string> &wordDict); [OK]

Hint: Ampersand & goes between type and variable name [OK]

Common Mistakes:

• Placing & after variable name incorrectly
• Missing semicolon at function declaration
• Using invalid syntax like wordDict&

3. What is the output of the following C++ code snippet?

bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

int main() {
    string s = "leetcode";
    vector<string> wordDict = {"leet", "code"};
    cout << (wordBreak(s, wordDict) ? "true" : "false") << endl;
    return 0;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Understand the dynamic programming logic

   The code uses a boolean vector dp where dp[i] is true if substring s[0..i-1] can be segmented into dictionary words. It initializes dp[0] as true (empty string).

2. Step 2: Trace the example input "leetcode" with dictionary ["leet", "code"]

   At i=4, substring "leet" is in dictionary, so dp[4] = true. At i=8, substring "code" is in dictionary and dp[4] is true, so dp[8] = true. Finally, dp[s.size()] = true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   DP segmentation confirms full string = true [OK]

Hint: Check dp array for full string index true [OK]

Common Mistakes:

• Confusing substring indices
• Forgetting to break inner loop after true
• Misunderstanding dp initialization

4. Identify the bug in the following C++ code for the Word Break Problem:

bool wordBreak(string s, vector<string> &wordDict) {
    unordered_set<string> dict(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size(), false);
    dp[0] = true;
    for (int i = 1; i <= s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && dict.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.size()];
}

medium

A. dp[0] should be initialized to false

B. dp vector size should be s.size() + 1, not s.size()

C. The substring indices in s.substr are incorrect

D. unordered_set should be a vector instead

Solution

1. Step 1: Check dp vector size and indexing

   The dp vector is sized to s.size(), but the code accesses dp[s.size()] which is out of bounds. It should be sized s.size() + 1 to include the base case for empty substring.

2. Step 2: Verify other parts

   unordered_set usage and substring indices are correct. dp[0] must be true to represent empty string segmentation.

3. Final Answer:

   dp vector size should be s.size() + 1, not s.size() -> Option B

4. Quick Check:

   dp size off by one causes runtime error [OK]

Hint: dp size = string length + 1 for base case [OK]

Common Mistakes:

• Using dp size equal to string length only
• Misinitializing dp[0] to false
• Confusing substring parameters

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm allows it to also return the actual segmented sentence "apple pen apple" instead of just true or false?

hard

A. Use a stack to store indices and print words in reverse order after DP

B. Return the count of possible segmentations instead of a boolean

C. Modify the dictionary to include spaces between words

D. Use a vector of strings to store sentences at each index and build them during DP

Solution

1. Step 1: Understand the limitation of boolean DP

   The standard Word Break DP returns only true/false indicating if segmentation is possible, but does not store the actual segmented sentences.

2. Step 2: Modify DP to store sentences

   By using a vector of strings at each dp index, we can store all possible sentences formed up to that index. When a valid word is found, append it to sentences from previous indices.

3. Step 3: Final answer

   This approach allows reconstructing the segmented sentence like "apple pen apple".

4. Final Answer:

   Use a vector of strings to store sentences at each index and build them during DP -> Option D

5. Quick Check:

   Store sentences in DP to reconstruct output [OK]

Hint: Store sentences in DP array to reconstruct segmentation [OK]

Common Mistakes:

• Trying to modify dictionary words
• Returning count instead of sentences
• Using stack without DP sentence storage