Word Break medium

Problem Statement

Given a string s and a dictionary of strings wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2

Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.

Steps

The problem can be solved efficiently using dynamic programming. We'll create a boolean array dp where dp[i] is true if the substring s.substring(0, i) can be segmented into words from wordDict.

  1. Initialization: dp[0] is true because an empty string can always be segmented.

  2. Iteration: We iterate through the string s from index 1 to the end. For each index i, we check if dp[i] can be made true.

  3. Check for segmentation: For each index i, we iterate through all possible breakpoints j from 0 to i - 1. If dp[j] is true (meaning the substring from 0 to j can be segmented) and the substring from j to i is in wordDict, then we set dp[i] to true.

  4. Result: dp[s.length()] will indicate whether the entire string s can be segmented.

Explanation

The dynamic programming approach avoids redundant calculations. We build up a solution by solving smaller subproblems first. dp[i] depends only on the values of dp[j] where j < i. This bottom-up approach ensures that when we consider a substring, we already know whether its prefixes can be segmented. The use of a HashSet for wordDict allows for O(1) lookup time, improving efficiency.

Code

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

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

Complexity

  • Time Complexity: O(n^2), where n is the length of the string s. This is because of the nested loops. The inner loop iterates up to i times in each outer loop iteration.
  • Space Complexity: O(n), due to the dp array of size n + 1. The wordSet HashSet has space complexity related to the size of the wordDict, but this is considered constant in relation to the length of the input string s.