Word Break Problem in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Word Break Problem?

The Word Break Problem asks if a given string can be segmented 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 Trie is commonly used to store the dictionary for fast word lookup.

intermediate

Explain the dynamic programming approach for the Word Break Problem.

Use a boolean array dp where dp[i] is true if substring(0, i) can be segmented. For each position i, check all j < i where dp[j] is true and substring(j, i) is in dictionary. If yes, set dp[i] true.

intermediate

What is the time complexity of the dynamic programming solution for the Word Break Problem?

The time complexity is O(n^3) in the worst case, where n is the length of the string, due to substring checks and dictionary lookups.

intermediate

Why is it important to check dp[j] before checking substring(j, i) in the DP solution?

Checking dp[j] ensures that the substring before j can be segmented, so only then we check if substring(j, i) is a dictionary word to build a valid segmentation.

In the Word Break Problem, what does dp[i] represent in the dynamic programming solution?

A Whether substring(i, end) is a dictionary word

B Length of the longest word ending at i

C Number of dictionary words in substring(0, i)

D Whether substring(0, i) can be segmented into dictionary words

dp[i] is true if the substring from start to i can be segmented into dictionary words.

Which data structure is best for fast dictionary word lookup in the Word Break Problem?

A LinkedList

B ArrayList

C HashSet

D Stack

HashSet provides O(1) average time complexity for word lookup.

What is the first step in the dynamic programming approach to the Word Break Problem?

A Initialize dp array with false except dp[0] = true

B Sort the dictionary words

C Reverse the input string

D Build a Trie from the dictionary

dp[0] = true means empty string can be segmented, which is the base case.

If dp[j] is false, what should you do when checking substring(j, i)?

A Check if substring(j, i) is in dictionary

B Skip checking substring(j, i)

C Set dp[i] to true immediately

D Reset dp array

If dp[j] is false, substring(0, j) can't be segmented, so no need to check substring(j, i).

What does it mean if dp[s.length()] is true after processing?

A The entire string can be segmented into dictionary words

B The string cannot be segmented

C Only the first half can be segmented

D The dictionary is empty

dp[s.length()] true means substring(0, s.length()) can be segmented fully.

Describe the dynamic programming approach to solve the Word Break Problem step-by-step.

Think about how to build solutions for smaller substrings to solve the whole problem.

Explain why using a HashSet for the dictionary improves the Word Break Problem solution.

Consider how often you check if a substring is in the dictionary.

Practice

1. What is the main goal of the Word Break Problem in algorithms?

easy

A. To check if a string can be segmented into valid dictionary words

B. To find the longest word in a dictionary

C. To count the number of vowels in a string

D. To reverse the characters of a string

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the goal

   The goal is to verify if such segmentation is possible, not to count or reverse characters.

3. Final Answer:

   To check if a string can be segmented into valid dictionary words -> Option A

4. Quick Check:

   Word Break Problem = Check segmentation [OK]

Hint: Remember: Word Break checks segmentation possibility [OK]

Common Mistakes:

• Confusing with string reversal
• Thinking it counts vowels
• Assuming it finds longest word

2. Which of the following Java method signatures is correct for a function solving the Word Break Problem?

easy

A. public int wordBreak(String s, Set<String> wordDict)

B. public boolean wordBreak(String s, List<String> wordDict)

C. public void wordBreak(String s, List<String> wordDict)

D. public String wordBreak(String s, Set<String> wordDict)

Solution

1. Step 1: Identify expected return type

   The Word Break Problem returns true or false, so return type should be boolean.

2. Step 2: Check parameter types

   The input string is String, and dictionary can be List or Set of strings. public boolean wordBreak(String s, List<String> wordDict) uses List<String> and boolean return, which is correct.

3. Final Answer:

   public boolean wordBreak(String s, List<String> wordDict) -> Option B

4. Quick Check:

   Return type boolean + List parameter = public boolean wordBreak(String s, List<String> wordDict) [OK]

Hint: Word Break returns boolean, input dictionary can be List or Set [OK]

Common Mistakes:

• Using int or void as return type
• Returning String instead of boolean
• Using wrong parameter types

3. What will be the output of the following Java code snippet?

import java.util.*;
public class Solution {
  public static boolean wordBreak(String s, List<String> wordDict) {
    boolean[] dp = new boolean[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))) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[s.length()];
  }
  public static void main(String[] args) {
    List<String> dict = Arrays.asList("leet", "code");
    System.out.println(wordBreak("leetcode", dict));
  }
}

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Understand the dynamic programming logic

   The dp array tracks if substring up to index i can be segmented. Initially dp[0] = true.

2. Step 2: Trace the input "leetcode" with dictionary ["leet", "code"]

   "leet" matches s[0:4], so dp[4] = true. Then "code" matches s[4:8], so dp[8] = true. Hence, dp[s.length()] = true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   "leetcode" segmented = true [OK]

Hint: Check dp array updates for substring matches [OK]

Common Mistakes:

• Assuming false because of substring indexing
• Confusing dp array meaning
• Ignoring break after setting dp[i]

4. Identify the bug in this Java code for the Word Break Problem:

public boolean wordBreak(String s, List<String> wordDict) {
  boolean[] dp = new boolean[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))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length()];
}

medium

A. substring indices are reversed

B. dp[0] should be false initially

C. dp array size should be s.length() + 1

D. wordDict should be a Set, not List

Solution

1. Step 1: Check dp array size and indexing

   The dp array must have length s.length() + 1 to include dp[0] and dp[s.length()] indices.

2. Step 2: Identify impact of incorrect dp size

   With size s.length(), dp[s.length()] access causes ArrayIndexOutOfBoundsException.

3. Final Answer:

   dp array size should be s.length() + 1 -> Option C

4. Quick Check:

   dp size = s.length()+1 fixes index error [OK]

Hint: dp array length = string length + 1 [OK]

Common Mistakes:

• Setting dp[0] false breaks base case
• Misusing substring indices
• Thinking List vs Set causes error here

5. Given the dictionary ["apple", "pen", "applepen", "pine", "pineapple"], which of the following strings can be segmented into dictionary words using the Word Break algorithm?

hard

A. "penpineappleapplepens"

B. "pineapplepenapples"

C. "applepinepens"

D. "pineapplepenapple"

Solution

1. Step 1: Analyze string "pineapplepenapple" segmentation

   It can be segmented as "pine" + "apple" + "pen" + "apple" or "pineapple" + "pen" + "apple" all in dictionary.

2. Step 2: Check other options for invalid segments

   The strings in A, B, and C contain substrings like "pens" or "apples" that cannot be segmented using the dictionary words (e.g., A and C end with "pens", B ends with "apples"). Only D can be fully segmented.

3. Final Answer:

   "pineapplepenapple" -> Option D

4. Quick Check:

   Valid segmentation = "pineapplepenapple" [OK]

Hint: Check each substring against dictionary words carefully [OK]

Common Mistakes:

• Assuming plural forms are valid
• Ignoring order of words
• Not verifying full segmentation