Word Break Problem in DSA Java

Mental Model

We want to check if a sentence can be split into valid words from a dictionary. We try breaking the sentence at every position and see if the parts are valid.

Analogy: Imagine you have a long chain of beads with letters. You want to cut the chain into smaller chains where each smaller chain is a known word from your dictionary.

sentence: w o r d b r e a k
positions: 0 1 2 3 4 5 6 7 8 9 10
Try cuts: [0|word|break|10]

Dry Run Walkthrough

Input: sentence: "leetcode", dictionary: ["leet", "code"]

Goal: Determine if "leetcode" can be segmented into words from the dictionary

Step 1: Check substring from index 0 to 4: "leet" is in dictionary

dp[0]=true, dp[4]=true ("leet" found)

Why: If substring "leet" is valid, mark dp[4] true to indicate valid segmentation up to index 4

Step 2: Check substring from index 4 to 8: "code" is in dictionary

dp[4]=true, dp[8]=true ("code" found)

Why: Since dp[4] is true and "code" is valid, mark dp[8] true meaning full sentence can be segmented

Step 3: Check dp at end index 8: dp[8] is true

dp array: [true, false, false, false, true, false, false, false, true]

Why: True at dp[8] means entire sentence can be segmented into dictionary words

Result:

dp array: [true, false, false, false, true, false, false, false, true]
Answer: true ("leetcode" can be segmented as "leet code")

Annotated Code

DSA Java

import java.util.*;

public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true; // empty string is valid

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true; // mark valid segmentation up to i
                    break; // no need to check further splits for i
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");
        boolean result = wordBreak(s, wordDict);
        System.out.println(result);
    }
}

dp[0] = true; // empty string is valid

Initialize dp to mark empty string as valid segmentation base

for (int i = 1; i <= s.length(); i++) {

Check all substring end positions from 1 to length

for (int j = 0; j < i; j++) {

Try all split points before i

if (dp[j] && wordSet.contains(s.substring(j, i))) {

If substring s[j:i] is in dictionary and dp[j] is true, mark dp[i] true

dp[i] = true; // mark valid segmentation up to i

Mark dp[i] true because valid segmentation found

break; // no need to check further splits for i

Stop checking splits for i once valid segmentation found

return dp[s.length()];

Return if full string can be segmented

Output

true

Complexity Analysis

Time: O(n^2) because for each position i, we check all previous positions j to find valid splits

Space: O(n) for the dp array that stores segmentation validity up to each index

vs Alternative: Naive recursion without memoization can be exponential; DP reduces repeated work to polynomial time

Edge Cases

Empty string input

Returns true because empty string can be segmented trivially

DSA Java

dp[0] = true; // empty string is valid

String with no valid segmentation

Returns false as no combination of dictionary words can form the string

DSA Java

if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; }

Dictionary contains single character words

Algorithm still works by checking all splits, including single characters

DSA Java

wordSet.contains(s.substring(j, i))

When to Use This Pattern

When you need to check if a string can be split into valid dictionary words, use the Word Break pattern with dynamic programming to efficiently test all segmentations.

Common Mistakes

Mistake: Not initializing dp[0] to true, causing all dp values to remain false
Fix: Set dp[0] = true to represent empty string as valid base case

Mistake: Not breaking inner loop after finding a valid split, causing unnecessary checks
Fix: Add break after dp[i] = true to stop further checks for current i

Mistake: Using list lookup instead of set for dictionary, causing slow contains checks
Fix: Convert dictionary list to HashSet for O(1) lookup

Summary

Checks if a string can be segmented into a sequence of dictionary words.

Use when you want to verify if a sentence can be formed by concatenating known words.

The key is to use a boolean array to remember valid segmentations up to each index.

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