Word Break - Java Solution

1. Introduction

This blog post discusses the "Word Break" problem, a classic problem in dynamic programming. The problem involves determining if a given string can be segmented into a sequence of words found in a given dictionary. This is a common problem in parsing and text processing, where we need to understand if a string can be composed of valid words from a known set.

Problem

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, the task is to return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same word in the dictionary may be reused multiple times in the segmentation.

2. Solution Steps

1. Use dynamic programming to solve the problem.

2. Create a boolean array dp with a length of s.length() + 1, where dp[i] indicates whether the first i characters of s can be segmented into dictionary words.

3. Set dp[0] to true, as an empty string can always be segmented.

4. Iterate through the string, and for each index i, check every substring ending at i to see if it can be segmented.

5. If any such substring can be segmented (i.e., both the substring and the remaining part of s are valid), set dp[i] to true.

6. Return the value of dp[s.length()].

3. Code Program

import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class WordBreak {
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = List.of("leet", "code");
        System.out.println(wordBreak(s, wordDict)); // Test the function
    }

    // Function to determine if a string can be segmented into words from a dictionary
    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;

        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;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

Output:

true

Explanation:

1. wordBreak: This function checks if the string s can be segmented into a sequence of words found in the dictionary wordDict.

2. It converts wordDict into a HashSet for efficient lookup.

3. The dp array is used to keep track of whether the substring of s ending at each index i can be segmented.

4. For each i, the function iterates through all substrings ending at i and checks if any of these substrings and the remaining string form valid segments.

5. If a valid segmentation is found, dp[i] is set to true.

6. The function returns dp[s.length()], indicating whether the entire string s can be segmented.

7. This approach efficiently determines the segmentation by breaking down the problem into subproblems and using dynamic programming to avoid redundant calculations.