Word Break Problem in DSA Java - Execution Trace

Concept Flow - Word Break Problem

Start

↓

Initialize DP array

↓

For each index i in string

↓

For each index j < i

↓

Check if substring(j, i) in dictionary AND dp[j

Yes↓

Set dp[i

↓

Break inner loop

↓

Continue outer loop

↓

End

↓

Return dp[string length

We start by creating a boolean array to track if substrings can be formed from dictionary words. We check all substrings and update the array accordingly until we reach the end.

Execution Sample

DSA Java

String s = "leetcode";
Set<String> dict = Set.of("leet", "code");
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;
    }
  }
}
System.out.println(dp[s.length()]);

This code checks if the string "leetcode" can be segmented into words from the dictionary {"leet", "code"} using dynamic programming.

Execution Table

Step	Operation	Substring Checked	dp Array State	Action	Visual State
0	Initialize dp[0]	""	[true, false, false, false, false, false, false, false, false]	Set dp[0] = true	dp: [T, F, F, F, F, F, F, F, F]
1	i=1, j=0	s[0:1] = "l"	[true, false, false, false, false, false, false, false, false]	Not in dict, dp[1] remains false	dp: [T, F, F, F, F, F, F, F, F]
2	i=2, j=0..1	s[0:2] = "le", s[1:2] = "e"	[true, false, false, false, false, false, false, false, false]	No matches, dp[2] false	dp: [T, F, F, F, F, F, F, F, F]
3	i=3, j=0..2	s[0:3] = "lee", s[1:3] = "ee", s[2:3] = "e"	[true, false, false, false, false, false, false, false, false]	No matches, dp[3] false	dp: [T, F, F, F, F, F, F, F, F]
4	i=4, j=0..3	s[0:4] = "leet", s[1:4] = "eet", s[2:4] = "et", s[3:4] = "t"	[true, false, false, false, false, false, false, false, false]	Found "leet" and dp[0] true, set dp[4] = true	dp: [T, F, F, F, T, F, F, F, F]
5	i=5, j=0..4	s[0:5] = "leetc", ..., s[4:5] = "c"	[true, false, false, false, true, false, false, false, false]	No matches, dp[5] false	dp: [T, F, F, F, T, F, F, F, F]
6	i=6, j=0..5	s[0:6] = "leetco", ..., s[5:6] = "o"	[true, false, false, false, true, false, false, false, false]	No matches, dp[6] false	dp: [T, F, F, F, T, F, F, F, F]
7	i=7, j=0..6	s[0:7] = "leetcod", ..., s[6:7] = "d"	[true, false, false, false, true, false, false, false, false]	No matches, dp[7] false	dp: [T, F, F, F, T, F, F, F, F]
8	i=8, j=0..7	s[0:8] = "leetcode", ..., s[4:8] = "code"	[true, false, false, false, true, false, false, false, false]	Found "code" and dp[4] true, set dp[8] = true	dp: [T, F, F, F, T, F, F, F, T]
9	End	-	[true, false, false, false, true, false, false, false, true]	Return dp[8] = true	Final dp: [T, F, F, F, T, F, F, F, T]

💡 Reached end of string; dp[s.length()] is true, so string can be segmented.

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 8	Final
dp	[T, F, F, F, F, F, F, F, F]	[T, F, F, F, F, F, F, F, F]	[T, F, F, F, T, F, F, F, F]	[T, F, F, F, T, F, F, F, T]	[T, F, F, F, T, F, F, F, T]
i	0	1	4	8	8
j	-	0	0	4	-

Key Moments - 3 Insights

Why do we set dp[0] = true at the start?

dp[0] = true means the empty string can be segmented. This is the base case allowing us to build solutions for longer substrings. See execution_table step 0.

Why do we break the inner loop once dp[i] is set to true?

Once dp[i] is true, it means substring s[0:i] can be segmented, so no need to check other j values. This saves time. See execution_table step 4 and 8.

What does dp[i] = true represent?

dp[i] = true means the substring s[0:i] can be segmented into dictionary words. This is shown in execution_table's dp array state after each step.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What substring caused dp[4] to become true?

A "leet"

B "code"

C "lee"

D "t"

💡 Hint

Check the 'Substring Checked' and 'Action' columns at step 4 in execution_table.

At which step does dp[8] become true indicating the whole string can be segmented?

A Step 5

B Step 8

C Step 7

D Step 9

💡 Hint

Look at the 'dp Array State' and 'Action' columns for step 8 in execution_table.

If the dictionary did not contain "code", what would dp[8] be at the end?

A true

B null

C false

D undefined

💡 Hint

Refer to variable_tracker dp array final state and understand that without "code", dp[8] would not be set true.

Concept Snapshot

Word Break Problem:
- Use a boolean dp array of length s+1.
- dp[0] = true (empty string base case).
- For each i, check all j < i.
- If dp[j] is true and s[j:i] in dict, set dp[i] = true.
- Result is dp[s.length()].

Full Transcript

The Word Break Problem checks if a string can be split into dictionary words. We use a boolean array dp where dp[i] means substring s[0:i] can be segmented. We start with dp[0] = true for the empty string. For each position i, we check all previous positions j. If dp[j] is true and substring s[j:i] is in the dictionary, we set dp[i] to true and stop checking further j for that i. After filling dp, dp[s.length()] tells if the whole string can be segmented. For example, "leetcode" with dictionary {"leet", "code"} results in dp[8] = true, meaning it can be segmented as "leet" + "code".

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