Word Break Problem in DSA C# - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string without spaces, like a sentence with all words stuck together. You want to check if this string can be split into valid words from a dictionary.

🎯 Goal: Build a program that checks if a given string can be segmented into a sequence of dictionary words using the Word Break algorithm.

📋 What You'll Learn

Create a list of dictionary words

Create a string variable for the input text

Implement the Word Break logic using dynamic programming

Print true if the string can be segmented, otherwise false

💡 Why This Matters

🌍 Real World

This technique is used in text processing, spell checking, and natural language processing to split words correctly.

💼 Career

Understanding dynamic programming and string manipulation is important for software development roles involving algorithms and data processing.

1

Create the dictionary list

Create a list of strings called dictionary with these exact words: "apple", "pen", "pine", "pineapple"

DSA C#

# Your code here

Hint

Use List<string> and initialize it with the given words inside curly braces.

2

Create the input string

Add a string variable called input and set it to "pineapplepenapple"

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List dictionary = new List { "apple", "pen", "pine", "pineapple" };
        // Your code here
    }
}

Hint

Declare a string variable named input and assign the exact text.

3

Implement the Word Break logic

Add code to create a boolean array called dp of size input.Length + 1. Set dp[0] to true. Use a for loop with variable i from 1 to input.Length. Inside it, use another for loop with variable j from 0 to i. Check if dp[j] is true and the substring input.Substring(j, i - j) is in dictionary. If yes, set dp[i] to true and break the inner loop.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List dictionary = new List { "apple", "pen", "pine", "pineapple" };
        string input = "pineapplepenapple";
        // Implement Word Break logic here
    }
}

Hint

Use two nested loops and update the dp array based on substring checks.

4

Print the result

Add a Console.WriteLine statement to print the value of dp[input.Length].

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List dictionary = new List { "apple", "pen", "pine", "pineapple" };
        string input = "pineapplepenapple";

        bool[] dp = new bool[input.Length + 1];
        dp[0] = true;

        for (int i = 1; i <= input.Length; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (dp[j] && dictionary.Contains(input.Substring(j, i - j)))
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        // Print the result here
    }
}

Hint

Use Console.WriteLine(dp[input.Length]) to print the final boolean result.

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