Word Break Problem in DSA C#

Mental Model

We want to check if a sentence can be split into valid words from a dictionary. We try breaking the sentence at every position and see if the parts are valid.

Analogy: Imagine you have a long necklace made of beads without spaces. You want to cut it into smaller necklaces where each smaller necklace is a known pattern you recognize.

sentence: w o r d b r e a k
positions: 0 1 2 3 4 5 6 7 8 9 10
check cuts at each position ->

Dry Run Walkthrough

Input: sentence: "leetcode", dictionary: ["leet", "code"]

Goal: Determine if "leetcode" can be segmented into words from the dictionary

Step 1: Check substring from start 0 to 3: "leet" is in dictionary

dp[0]=true, dp[4]=true (since "leet" is valid)

Why: We mark dp[4] true because the first 4 letters form a valid word

Step 2: Check substring from start 4 to 7: "code" is in dictionary and dp[4] is true

dp[8]=true (whole string can be segmented)

Why: Since dp[4] is true and "code" is valid, the whole string is segmentable

Step 3: No other splits needed as dp[8] is true

dp array: [true, false, false, false, true, false, false, false, true]

Why: dp at last index true means sentence can be segmented

Result:

dp array: [true, false, false, false, true, false, false, false, true]
Answer: true

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class WordBreak {
    public static bool CanSegment(string s, IList<string> wordDict) {
        var wordSet = new HashSet<string>(wordDict);
        bool[] dp = new bool[s.Length + 1];
        dp[0] = true; // empty string can be segmented

        for (int i = 1; i <= s.Length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break; // found a valid segmentation
                }
            }
        }
        return dp[s.Length];
    }

    static void Main() {
        string s = "leetcode";
        IList<string> dict = new List<string>{"leet", "code"};
        bool result = CanSegment(s, dict);
        Console.WriteLine(result);
    }
}

dp[0] = true; // empty string can be segmented

Initialize dp for empty string as true

for (int i = 1; i <= s.Length; i++) {

Check all substring lengths from 1 to full string length

for (int j = 0; j < i; j++) {

Try all split points for substring s[0..i-1]

if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) {

If prefix s[0..j-1] can be segmented and s[j..i-1] is a word, mark dp[i] true

dp[i] = true;

Mark current position as segmentable

break; // found a valid segmentation

Stop checking further splits for this i

return dp[s.Length];

Return if full string can be segmented

Output

True

Complexity Analysis

Time: O(n^2) because we check all substring splits for each position in the string

Space: O(n) for the dp array that stores segmentation status up to each index

vs Alternative: Naive recursion without memoization can be exponential; DP reduces repeated work to polynomial time

Edge Cases

Empty string

Returns true because empty string can be segmented trivially

DSA C#

dp[0] = true; // empty string can be segmented

String with no valid segmentation

Returns false as no combination of dictionary words can form the string

DSA C#

if (dp[j] && wordSet.Contains(s.Substring(j, i - j))) { dp[i] = true; break; }

Dictionary contains words that are substrings of others

Algorithm correctly finds segmentation by checking all splits

DSA C#

for (int j = 0; j < i; j++) { ... }

When to Use This Pattern

When you need to check if a string can be split into dictionary words, use the Word Break DP pattern to efficiently test all segmentations.

Common Mistakes

Mistake: Not initializing dp[0] to true, causing all checks to fail
Fix: Set dp[0] = true to represent empty string segmentation

Mistake: Checking substrings incorrectly with wrong indices
Fix: Use s.Substring(j, i - j) to get substring from j to i-1

Summary

Checks if a string can be segmented into valid dictionary words using dynamic programming.

Use when you want to verify if a sentence can be split into known words without rearranging letters.

The key insight is to build up a boolean array where each position marks if the substring up to that point can be segmented.

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