Word Break Problem in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Word Break Check

What is the output of the following Java code that checks if the string can be segmented into dictionary words?

DSA Java

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, Set<String> dict) {
        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] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    public static void main(String[] args) {
        Set<String> dict = new HashSet<>(Arrays.asList("apple", "pen"));
        System.out.println(wordBreak("applepenapple", dict));
    }
}

A true

B false

C Compilation error

D Runtime exception

💡 Hint

Think about whether the string can be split into dictionary words.

The string "applepenapple" can be segmented as "apple" + "pen" + "apple", all present in the dictionary, so the output is true.

❓ Predict Output

intermediate

Output for Unbreakable String

What will be the output of this Java code when the string cannot be segmented into dictionary words?

DSA Java

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, Set<String> dict) {
        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] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    public static void main(String[] args) {
        Set<String> dict = new HashSet<>(Arrays.asList("cats", "dog", "sand", "and", "cat"));
        System.out.println(wordBreak("catsandog", dict));
    }
}

A false

B Runtime exception

C Compilation error

D true

💡 Hint

Check if the string can be fully segmented using the dictionary words.

The string "catsandog" cannot be segmented fully into the dictionary words because "og" is not in the dictionary, so output is false.

🧠 Conceptual

advanced

Understanding DP Array in Word Break

In the Word Break problem, what does the boolean array dp represent during the algorithm execution?

A dp[i] is true if the substring s[i..end] can be segmented into dictionary words

B dp[i] stores the length of the longest dictionary word ending at index i

C dp[i] is true if the substring s[0..i-1] can be segmented into dictionary words

D dp[i] counts the number of dictionary words found up to index i

💡 Hint

Think about what the index i in dp corresponds to in the string.

dp[i] is true if the substring from start to i-1 can be segmented into dictionary words, helping build solutions for longer substrings.

🔧 Debug

advanced

Identify the Bug in Word Break Code

What error will this Java code produce when run, and why?

DSA Java

import java.util.*;
public class WordBreak {
    public static boolean wordBreak(String s, Set<String> dict) {
        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] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    public static void main(String[] args) {
        Set<String> dict = new HashSet<>(Arrays.asList("apple", "pen"));
        System.out.println(wordBreak("applepenapple", dict));
    }
}

A Compilation error due to missing import

B ArrayIndexOutOfBoundsException at dp[i] assignment

C NullPointerException due to uninitialized dp array

D No error, outputs true

💡 Hint

Check the size of dp array and the indices used to access it.

The dp array size is s.length(), but code accesses dp[s.length()] which is out of bounds causing ArrayIndexOutOfBoundsException.

🚀 Application

expert

Count Number of Ways to Segment String

Given the Word Break problem, which code snippet correctly counts the number of ways to segment the string into dictionary words?

A int[] dp = new int[s.length()]; dp[0] = 1; for (int i = 1; i < s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] > 0 && dict.contains(s.substring(j, i))) { dp[i] = dp[j]; } } } return dp[s.length() - 1];

B boolean[] dp = new boolean[s.length() + 1]; dp[0] = true; int count = 0; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; count++; } } } return count;

C int count = 0; for (int i = 0; i < s.length(); i++) { if (dict.contains(s.substring(0, i))) count++; } return count;

D int[] dp = new int[s.length() + 1]; dp[0] = 1; for (int i = 1; i <= s.length(); i++) { for (int j = 0; j < i; j++) { if (dp[j] > 0 && dict.contains(s.substring(j, i))) { dp[i] += dp[j]; } } } return dp[s.length()];

💡 Hint

Count ways requires summing counts from valid previous breaks, not just boolean flags.

Option D uses an integer dp array to accumulate counts of ways to segment prefixes, correctly summing counts from valid previous indices.

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