Word Break Problem in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the input string is empty.

DSA Java

if (s.[1]()) {
    return true;
}

Drag options to blanks, or click blank then click option'

AisEmpty

Blength

Cequals

Dsubstring

Attempts:

3 left

💡 Hint

Common Mistakes

Using length() instead of isEmpty()

Using equals() which compares strings

Using substring() which extracts parts of the string

The method isEmpty() returns true if the string has zero length, which means it's empty.

2fill in blank

medium

Complete the code to check if the string starts with a dictionary word.

DSA Java

if (s.[1](word)) {
    // proceed
}

Drag options to blanks, or click blank then click option'

AstartsWith

Bcontains

CendsWith

Dequals

Attempts:

3 left

💡 Hint

Common Mistakes

Using contains() which checks anywhere in the string

Using endsWith() which checks the end of the string

Using equals() which checks full string equality

startsWith(word) checks if the string s begins with the substring word.

3fill in blank

hard

Fix the error in the recursive call to check the remaining substring.

DSA Java

if (wordBreak(s.[1](word.length()), wordDict)) {
    return true;
}

Drag options to blanks, or click blank then click option'

Asubstr

BsubString

Cslice

Dsubstring

Attempts:

3 left

💡 Hint

Common Mistakes

Using subString() with uppercase 'S' causes a compile error

Using substr() or slice() which are not Java String methods

substring() is the correct Java method to get a part of the string starting from an index.

4fill in blank

hard

Fill both blanks to create a loop that checks each word in the dictionary.

DSA Java

for (String [1] : [2]) {
    // check word
}

Drag options to blanks, or click blank then click option'

Aword

Bs

CwordDict

Ddict

Attempts:

3 left

💡 Hint

Common Mistakes

Using 's' which is the input string, not the dictionary

Using 'dict' which is not defined in the code

The loop variable is 'word' and the collection to iterate is 'wordDict'.

5fill in blank

hard

Fill all three blanks to build a memoization map that stores results.

DSA Java

Map<String, Boolean> [1] = new HashMap<>();

if ([2].containsKey(s)) {
    return [3].get(s);
}

Drag options to blanks, or click blank then click option'

Amemo

Dcache

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causing errors

Using 'cache' inconsistently

The memoization map is named 'memo' and is used to check and get stored results.

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