Word Break Problem in DSA C# - Execution Trace

Concept Flow - Word Break Problem

Start

↓

Initialize DP array

↓

For each index i in string

↓

For each j from 0 to i

↓

Check if substring(j, i) in dictionary AND dp[j

Yes↓

Set dp[i

↓

Break inner loop

↓

Continue outer loop

↓

End

↓

Return dp[string length

We use a boolean array to track if substrings can be formed from dictionary words. For each position, we check all previous positions to see if a valid word ends there.

Execution Sample

DSA C#

string s = "leetcode";
var dict = new HashSet<string>{"leet", "code"};
bool[] dp = new bool[s.Length + 1];
dp[0] = true;
for (int i = 1; i <= s.Length; i++) {
  for (int j = 0; j < i; j++) {
    if (dp[j] && dict.Contains(s.Substring(j, i - j))) {
      dp[i] = true;
      break;
    }
  }
}
Console.WriteLine(dp[s.Length]);

This code checks if '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	Result
1	Initialize dp	-	-	-	[true, false, false, false, false, false, false, false, false]	Set dp[0] = true	dp[0] = true
2	i=1, j=0	1	0	"l"	[true, false, false, false, false, false, false, false, false]	Check dp[0] && dict.Contains("l")	False
3	i=2, j=0	2	0	"le"	[true, false, false, false, false, false, false, false, false]	Check dp[0] && dict.Contains("le")	False
4	i=2, j=1	2	1	"e"	[true, false, false, false, false, false, false, false, false]	Check dp[1] && dict.Contains("e")	False
5	i=3, j=0	3	0	"lee"	[true, false, false, false, false, false, false, false, false]	Check dp[0] && dict.Contains("lee")	False
6	i=3, j=1	3	1	"ee"	[true, false, false, false, false, false, false, false, false]	Check dp[1] && dict.Contains("ee")	False
7	i=3, j=2	3	2	"e"	[true, false, false, false, false, false, false, false, false]	Check dp[2] && dict.Contains("e")	False
8	i=4, j=0	4	0	"leet"	[true, false, false, false, false, false, false, false, false]	Check dp[0] && dict.Contains("leet")	True
9	Set dp[4] = true	4	0	"leet"	[true, false, false, false, true, false, false, false, false]	Update dp array	dp[4] = true
10	i=5, j=0	5	0	"leetc"	[true, false, false, false, true, false, false, false, false]	Check dp[0] && dict.Contains("leetc")	False
11	i=5, j=1	5	1	"eetc"	[true, false, false, false, true, false, false, false, false]	Check dp[1] && dict.Contains("eetc")	False
12	i=5, j=2	5	2	"etc"	[true, false, false, false, true, false, false, false, false]	Check dp[2] && dict.Contains("etc")	False
13	i=5, j=3	5	3	"tc"	[true, false, false, false, true, false, false, false, false]	Check dp[3] && dict.Contains("tc")	False
14	i=5, j=4	5	4	"c"	[true, false, false, false, true, false, false, false, false]	Check dp[4] && dict.Contains("c")	False
15	i=6, j=0	6	0	"leetco"	[true, false, false, false, true, false, false, false, false]	Check dp[0] && dict.Contains("leetco")	False
16	i=6, j=1	6	1	"eetco"	[true, false, false, false, true, false, false, false, false]	Check dp[1] && dict.Contains("eetco")	False
17	i=6, j=2	6	2	"etco"	[true, false, false, false, true, false, false, false, false]	Check dp[2] && dict.Contains("etco")	False
18	i=6, j=3	6	3	"tco"	[true, false, false, false, true, false, false, false, false]	Check dp[3] && dict.Contains("tco")	False
19	i=6, j=4	6	4	"co"	[true, false, false, false, true, false, false, false, false]	Check dp[4] && dict.Contains("co")	False
20	i=6, j=5	6	5	"o"	[true, false, false, false, true, false, false, false, false]	Check dp[5] && dict.Contains("o")	False
21	i=7, j=0	7	0	"leetcod"	[true, false, false, false, true, false, false, false, false]	Check dp[0] && dict.Contains("leetcod")	False
22	i=7, j=1	7	1	"eetcod"	[true, false, false, false, true, false, false, false, false]	Check dp[1] && dict.Contains("eetcod")	False
23	i=7, j=2	7	2	"etcod"	[true, false, false, false, true, false, false, false, false]	Check dp[2] && dict.Contains("etcod")	False
24	i=7, j=3	7	3	"tcod"	[true, false, false, false, true, false, false, false, false]	Check dp[3] && dict.Contains("tcod")	False
25	i=7, j=4	7	4	"cod"	[true, false, false, false, true, false, false, false, false]	Check dp[4] && dict.Contains("cod")	False
26	i=7, j=5	7	5	"od"	[true, false, false, false, true, false, false, false, false]	Check dp[5] && dict.Contains("od")	False
27	i=7, j=6	7	6	"d"	[true, false, false, false, true, false, false, false, false]	Check dp[6] && dict.Contains("d")	False
28	i=8, j=0	8	0	"leetcode"	[true, false, false, false, true, false, false, false, false]	Check dp[0] && dict.Contains("leetcode")	False
29	i=8, j=1	8	1	"eetcode"	[true, false, false, false, true, false, false, false, false]	Check dp[1] && dict.Contains("eetcode")	False
30	i=8, j=2	8	2	"etcode"	[true, false, false, false, true, false, false, false, false]	Check dp[2] && dict.Contains("etcode")	False
31	i=8, j=3	8	3	"tcode"	[true, false, false, false, true, false, false, false, false]	Check dp[3] && dict.Contains("tcode")	False
32	i=8, j=4	8	4	"code"	[true, false, false, false, true, false, false, false, false]	Check dp[4] && dict.Contains("code")	True
33	Set dp[8] = true	8	4	"code"	[true, false, false, false, true, false, false, false, true]	Update dp array	dp[8] = true
34	End	-	-	-	[true, false, false, false, true, false, false, false, true]	Return dp[s.Length]	True

💡 Loop ends after i=8; dp[8] is true meaning the string can be segmented.

Variable Tracker

Variable	Start	After Step 9	After Step 33	Final
dp	[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	4	8	8
j	-	0	4	4

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 that allows checking substrings starting from index 0, as seen in execution_table row 1.

Why do we break the inner loop once dp[i] is set to true?

Once dp[i] is true, it means substring up to i can be segmented. No need to check further j values for that i. This is shown in execution_table row 9 and 33 where after setting dp[i] true, inner loop breaks.

What does dp[i] represent in this problem?

dp[i] is true if substring s[0..i-1] can be segmented into dictionary words. For example, dp[4] = true means 'leet' can be segmented, as shown in execution_table row 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what substring is checked and what is the result?

A "leet", result true

B "leet", result false

C "code", result true

D "code", result false

💡 Hint

Refer to execution_table row 8 under 'Substring Checked' and 'Result' columns.

At which step does dp[8] become true indicating the whole string can be segmented?

A Step 28

B Step 9

C Step 33

D Step 1

💡 Hint

Check execution_table rows near the end for dp array updates.

If the dictionary did not contain "code", how would dp[8] change?

A dp[8] would still be true

B dp[8] would be false

C dp[4] would be false

D dp[0] would be false

💡 Hint

Look at how dp[8] depends on substring "code" in execution_table row 32.

Concept Snapshot

Word Break Problem:
- Use dp array of length s+1, dp[0] = true
- dp[i] = true if any dp[j] is true and s[j..i-1] in dictionary
- Nested loops: i from 1 to s.Length, j from 0 to i
- Return dp[s.Length] as result
- Break inner loop early when dp[i] is 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 substring up to i can be segmented. Start dp[0] as true for empty string. For each position i, check all previous positions j. If dp[j] is true and substring from j to i is in dictionary, set dp[i] true and break inner loop. After filling dp, dp[s.Length] tells if full string can be segmented. This dynamic programming approach efficiently solves the problem by building solutions for smaller substrings.

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. The longest word in wordDict that appears in s

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

C. The number of unique characters in s that are also in wordDict

D. Whether s is a palindrome

Solution

1. Step 1: Understand the problem statement

   The Word Break Problem asks if the string s can be split into words all found in the dictionary wordDict.

2. Step 2: Identify the correct description

   Whether s can be segmented into a space-separated sequence of one or more dictionary words correctly describes this segmentation check, while others describe unrelated tasks.

3. Final Answer:

   Whether 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 checks if string splits into dictionary words [OK]

Common Mistakes:

• Confusing Word Break with palindrome checking
• Thinking it counts characters instead of segmenting
• Assuming it finds longest word instead of segmentation

2. Which of the following C# method signatures is correct for a function solving the Word Break Problem that returns a boolean indicating if the string can be segmented?

easy

A. public string WordBreak(int s, IList<string> wordDict)

B. public int WordBreak(string s, List<int> wordDict)

C. public bool WordBreak(string s, IList<string> wordDict)

D. public bool WordBreak(string s, string wordDict)

Solution

1. Step 1: Check parameter types for Word Break

   The input string s should be a string, and the dictionary wordDict should be a list of strings.

2. Step 2: Verify return type and parameters

   public bool WordBreak(string s, IList<string> wordDict) matches the expected signature: returns bool, takes string and IList<string>. Others have wrong types or return types.

3. Final Answer:

   public bool WordBreak(string s, IList<string> wordDict) -> Option C

4. Quick Check:

   Correct method signature = public bool WordBreak(string s, IList<string> wordDict) [OK]

Hint: Return bool, input string and list of strings for dictionary [OK]

Common Mistakes:

• Using wrong return type like int or string
• Passing dictionary as string instead of list
• Using wrong parameter types like int for string

3. What will be the output of the following C# code snippet?

var s = "leetcode";
var wordDict = new List<string> { "leet", "code" };
var result = WordBreak(s, wordDict);
Console.WriteLine(result);

bool WordBreak(string s, IList<string> wordDict) {
    var dp = new bool[s.Length + 1];
    dp[0] = true;
    for (int i = 1; i <= s.Length; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordDict.Contains(s.Substring(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.Length];
}

medium

A. False

B. Runtime exception

C. Compilation error

D. True

Solution

1. Step 1: Understand the dynamic programming logic

   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 substring checks for "leetcode"

   "leet" and "code" are in wordDict. The code finds "leet" at start and then "code" after, so dp[s.Length] becomes true.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Substring segmentation found = True [OK]

Hint: Check dp array updates for substrings in dictionary [OK]

Common Mistakes:

• Assuming false because of substring indexing confusion
• Thinking code throws exception on substring
• Ignoring dp array meaning

4. Identify the bug in the following Word Break implementation and select the correct fix:

bool WordBreak(string s, IList<string> wordDict) {
    var dp = new bool[s.Length];
    dp[0] = true;
    for (int i = 1; i <= s.Length; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordDict.Contains(s.Substring(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.Length];
}

medium

A. Change dp array size to s.Length + 1 and initialize dp[0] = true

B. Change dp array to int[] instead of bool[]

C. Change substring parameters to s.Substring(i, j)

D. Remove the inner loop and check only j = 0

Solution

1. Step 1: Identify dp array size and indexing issue

   The dp array should have length s.Length + 1 to represent empty substring at dp[0]. Current dp size is s.Length, causing index errors.

2. Step 2: Fix dp initialization and size

   Changing dp to size s.Length + 1 and setting dp[0] = true fixes indexing and logic.

3. Final Answer:

   Change dp array size to s.Length + 1 and initialize dp[0] = true -> Option A

4. Quick Check:

   dp size and initialization fix = Change dp array size to s.Length + 1 and initialize dp[0] = true [OK]

Hint: dp array length = s.Length + 1 for empty substring base case [OK]

Common Mistakes:

• Using dp size s.Length causes index out of range
• Incorrect substring parameters
• Removing inner loop breaks logic

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm will correctly count the number of ways to segment s into dictionary words instead of just checking if segmentation is possible?

hard

A. Change dp array to int[], initialize dp[0] = 1, and update dp[i] += dp[j] when substring is in dictionary

B. Use a boolean dp array but return dp[s.Length] as integer count

C. Use recursion without memoization to count ways

D. Change dp array to string[] to store segmented sentences

Solution

1. Step 1: Understand difference between boolean and count dp

   Boolean dp tracks if segmentation is possible. To count ways, dp must store counts as integers.

2. Step 2: Modify dp to int[], initialize dp[0] = 1, and accumulate counts

   When substring s[j..i-1] is in dictionary, add dp[j] to dp[i] to count all ways.

3. Final Answer:

   Change dp array to int[], initialize dp[0] = 1, and update dp[i] += dp[j] when substring is in dictionary -> Option A

4. Quick Check:

   Counting ways requires int dp and accumulation [OK]

Hint: Use int dp and add counts for each valid substring [OK]

Common Mistakes:

• Using boolean dp for counting ways
• Returning boolean as integer count
• Ignoring memoization in recursion