[Leetcode] – Word Break Solution

17

In the given problem statement, we have a string s and a dictionary wordDict containing a list of words. We need to determine if s can be segmented into a space-separated sequence of dictionary words.

The tricky part of this problem is ensuring that every segment of the string matches words from the dictionary. A brute-force approach could generate all possible segmentations, but that would be highly inefficient.

Input: s = "studyalgorithms"
wordDict = ["study", "algorithms"]
Output: true
Explanation: Since "studyalgorithms" can be split into "study" and "algorithms", both of which are in the dictionary, the function should return true.

Input: s = "catsandog", 
wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: No possible combination of the dictionary words can be combined to get s. Full words are to be used

Brute Force Approach

The brute force approach involves checking all possible partitions of the string and verifying if each segment exists in the dictionary.

• Generate all possible segmentations of the string.
• For each segmentation, check if all the words exist in the dictionary.
• If a valid segmentation is found, return true.
• If no segmentation matches, return false.

This approach has a time complexity of O(2^n) due to the exponential number of possible partitions, making it impractical for large inputs.

Optimized Dynamic Programming Approach

To efficiently solve this problem, dynamic programming is used. The idea is to use a boolean array dp where dp[i] indicates whether the substring s[0..i] can be segmented using words from the dictionary.

Steps:

• Convert the dictionary into a set for O(1) lookups.
• Compute the maximum word length from the dictionary to optimize substring checks.
• Create a boolean array dp of size n+1 (where n is the length of s), initialized to false except dp[0], which is true (an empty string is always valid).
• Iterate over the string s and check for valid word breaks using dictionary words.
• Update dp[i] if a valid segmentation is found.
• The final answer is stored in dp[n].

Code

  boolean wordBreak(String s, List<String> wordDict) {

    // Convert the dictionary to a set for O(1) lookups
    Set<String> wordSet = new HashSet<>(wordDict);

    // Find the maximum word length in the dictionary
    int maxLen = 0;
    for (String word : wordDict) {
      maxLen = Math.max(maxLen, word.length());
    }

    int n = s.length();
    // dp[i] states if the substring s[0..i] can be segmented
    boolean[] dp = new boolean[n + 1];

    // Base case: empty string is valid
    dp[0] = true;

    for (int i = 1; i <= n; i++)

      // Check prefixes of length up to maxLen
      for (int j = i - 1; j >= Math.max(0, i - maxLen); j--)
        if (dp[j] && wordSet.contains(s.substring(j, i))) {
          dp[i] = true;
          break; // No need to check further prefixes
        }

    return dp[n];
  }
Code language: Java (java)

Time Complexity: O(n * maxLen), where n is the length of s and maxLen is the length of the longest word in the dictionary. Each substring check is optimized by restricting it to maxLen.
Space Complexity: O(n), used by the dp array.

By using dynamic programming, we significantly optimize the solution compared to brute force. The use of a dictionary set for lookups and limiting substring checks improves efficiency. This approach ensures that we can determine whether a string can be segmented efficiently, even for large inputs.

Video Explanation: