Word Break Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Break Check

What is the output of the following C# code that checks if the string can be segmented into dictionary words?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool WordBreak(string s, HashSet<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];
    }

    static void Main() {
        var dict = new HashSet<string> {"leet", "code"};
        string s = "leetcode";
        Console.WriteLine(WordBreak(s, dict));
    }
}

A Compilation error

B False

C True

D Runtime exception

💡 Hint

Think about whether the string "leetcode" can be split into words from the dictionary {"leet", "code"}.

The string "leetcode" can be segmented as "leet" + "code", both present in the dictionary, so the output is True.

❓ Predict Output

intermediate

Output for Unbreakable String

What will be printed by this C# program that tests word break for a string that cannot be segmented?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool WordBreak(string s, HashSet<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];
    }

    static void Main() {
        var dict = new HashSet<string> {"apple", "pen"};
        string s = "applepenapplex";
        Console.WriteLine(WordBreak(s, dict));
    }
}

A False

B True

C Compilation error

D Runtime exception

💡 Hint

Check if the string "applepenapplex" can be fully segmented using "apple" and "pen".

The string ends with 'x' which is not in the dictionary, so it cannot be segmented fully. The output is False.

🔧 Debug

advanced

Identify the Logical Error in Word Break Implementation

The following code attempts to solve the Word Break problem but produces incorrect results. What is the logical error?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static bool WordBreak(string s, HashSet<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 (dict.Contains(s.Substring(j, i - j))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.Length];
    }

    static void Main() {
        var dict = new HashSet<string> {"cats", "dog", "sand", "and", "cat"};
        string s = "catsanddog";
        Console.WriteLine(WordBreak(s, dict));
    }
}

A The code does not check if the prefix before the substring is breakable (missing dp[j] check).

B The dictionary is not initialized correctly.

C The substring indices are reversed causing runtime error.

D The dp array size is incorrect causing index out of range.

💡 Hint

Check the condition inside the inner loop carefully.

The code misses checking dp[j], which means it does not verify if the string before the current substring can be segmented. This causes incorrect true values.

🧠 Conceptual

advanced

Time Complexity of Word Break Algorithm

What is the time complexity of the dynamic programming solution for the Word Break problem where n is the length of the string and m is the number of words in the dictionary?

A O(n^3) because substring extraction and dictionary lookup inside nested loops

B O(n^2 * k) where k is average length of dictionary words due to substring and lookup

C O(n * m) because each position checks all dictionary words

D O(n^2) because of two nested loops and constant time dictionary lookup

💡 Hint

Consider substring extraction cost and dictionary lookup cost inside nested loops.

The outer loop runs n times, inner loop up to n times, substring extraction is O(k) where k is substring length (average word length), dictionary lookup is O(1). So total is O(n^2 * k).

🚀 Application

expert

Count All Possible Word Breaks

Given the string "catsanddog" and dictionary {"cat", "cats", "and", "sand", "dog"}, how many different ways can the string be segmented into dictionary words?

A 1

B 3

C 4

D 2

💡 Hint

Try to find all valid segmentations of the string using the dictionary words.

The string can be segmented as "cats and dog" and "cat sand dog" and "cat sanddog" is invalid because "sanddog" is not in dict. So total 2 ways. But careful: "catsanddog" can be segmented in 2 ways only.

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