Why Word Break Problem in DSA C#?

The Big Idea

What if you could instantly know if a jumbled string hides real words without guessing endlessly?

The Scenario

Imagine you have a long sentence without spaces, like a secret message: "applepenapple". You want to find out if it can be split into known words like "apple" and "pen".

The Problem

Trying every possible way to split the sentence by hand is slow and confusing. You might miss some splits or repeat the same checks many times, making it frustrating and error-prone.

The Solution

The Word Break Problem uses a smart way to check if the sentence can be split into dictionary words by remembering which parts work and which don't. This saves time and avoids repeated work.

Before vs After

✗ Before

bool CanSplit(string s, List<string> dict) {
  if (s.Length == 0) return true;
  for (int i = 1; i <= s.Length; i++) {
    string part = s.Substring(0, i);
    if (dict.Contains(part)) {
      if (CanSplit(s.Substring(i), dict)) return true;
    }
  }
  return false;
}

✓ After

bool CanSplit(string s, List<string> dict) {
  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;
      }
    }
  }
  return dp[s.Length];
}

What It Enables

This lets you quickly check if a long string can be split into valid words, enabling smart text processing like spell checking and auto-correction.

Real Life Example

When you type without spaces on your phone, the system uses this to guess where words start and end, so it can suggest corrections or split your text properly.

Key Takeaways

Manual splitting is slow and repeats work.

Dynamic programming remembers results to speed up checks.

Useful for text processing and word recognition tasks.

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