Word Break Problem in DSA Java - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string of letters without spaces, like a secret message. You want to check if you can split this string into words that you know from a dictionary.

🎯 Goal: You will write a program that checks if a given string can be broken into a sequence of dictionary words.

📋 What You'll Learn

Create a string variable for the input text

Create a list of strings as the dictionary

Use a boolean array to keep track of valid breaks

Implement the word break logic using loops

Print true if the string can be segmented, otherwise false

💡 Why This Matters

🌍 Real World

This problem helps in text processing like spell checking, word prediction, and natural language processing.

💼 Career

Understanding this problem is useful for software engineers working on search engines, text editors, and AI language models.

1

Create the input string and dictionary

Create a string variable called text with the value "applepenapple". Then create a list of strings called dictionary containing "apple" and "pen".

DSA Java

// Your code here

Hint

Use String text = "applepenapple"; and List dictionary = Arrays.asList("apple", "pen");

2

Create a boolean array to track valid breaks

Add a boolean array called dp with size text.length() + 1. Set dp[0] to true.

DSA Java

import java.util.*;

public class WordBreak {
    public static void main(String[] args) {
        String text = "applepenapple";
        List dictionary = Arrays.asList("apple", "pen");
        // Your code here
    }
}

Hint

Use boolean[] dp = new boolean[text.length() + 1]; and set dp[0] = true;

3

Implement the word break logic

Use nested for loops with variables i and j to check substrings of text. Inside the inner loop, check if dp[j] is true and if dictionary.contains(text.substring(j, i)). If both are true, set dp[i] to true.

DSA Java

import java.util.*;

public class WordBreak {
    public static void main(String[] args) {
        String text = "applepenapple";
        List dictionary = Arrays.asList("apple", "pen");
        boolean[] dp = new boolean[text.length() + 1];
        dp[0] = true;
        // Use nested for loops to fill dp array
        // Your code here
    }
}

Hint

Use two loops: for (int i = 1; i <= text.length(); i++) and for (int j = 0; j < i; j++). Inside, check if (dp[j] && dictionary.contains(text.substring(j, i))) then set dp[i] = true;

4

Print the result

Print the value of dp[text.length()] using System.out.println.

DSA Java

import java.util.*;

public class WordBreak {
    public static void main(String[] args) {
        String text = "applepenapple";
        List dictionary = Arrays.asList("apple", "pen");
        boolean[] dp = new boolean[text.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= text.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dictionary.contains(text.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        // Your code here
    }
}

Hint

Use System.out.println(dp[text.length()]); to print the result.

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