Word Break Problem in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Word Break Problem?

The Word Break Problem asks if a given string can be split into a sequence of one or more dictionary words.

beginner

What data structure is commonly used to store the dictionary in the Word Break Problem?

A HashSet or a Trie is commonly used to store dictionary words for fast lookup.

intermediate

What is the main approach to solve the Word Break Problem efficiently?

Dynamic Programming is used to check if substrings can be segmented into dictionary words, avoiding repeated work.

intermediate

In the DP solution, what does the boolean array represent?

Each position in the boolean array indicates if the substring up to that position can be segmented into dictionary words.

intermediate

Why is it important to check all possible partitions in the Word Break Problem?

Because the string can be segmented in multiple ways, checking all partitions ensures no valid segmentation is missed.

What does the Word Break Problem determine?

A If a string can be segmented into dictionary words

B If a string is a palindrome

C If a string contains only letters

D If a string is sorted alphabetically

The Word Break Problem checks if the string can be split into valid dictionary words.

Which technique is commonly used to solve the Word Break Problem efficiently?

A Greedy Algorithm

B Depth-First Search

C Dynamic Programming

D Breadth-First Search

Dynamic Programming helps avoid repeated checks by storing results of subproblems.

What does the boolean DP array represent in the Word Break Problem?

A If substring up to index can be segmented

B Length of the longest word

C Number of dictionary words

D Frequency of characters

Each boolean value shows if the substring up to that index can be formed from dictionary words.

Which data structure is best for fast dictionary word lookup?

A Stack

B Queue

C Linked List

D HashSet

HashSet provides O(1) average lookup time for dictionary words.

Why do we check all partitions of the string in the Word Break Problem?

A To sort the string

B To find all possible segmentations

C To count characters

D To reverse the string

Checking all partitions ensures no valid segmentation is missed.

Explain how dynamic programming helps solve the Word Break Problem.

Think about how you remember if parts of the string can be segmented.

Describe the steps to check if a string can be segmented using a dictionary.

Consider how you break the string into smaller pieces and verify each.

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