algoadvance

Leetcode 139. Word Break

Problem Statement

The “Word Break” problem can be found on LeetCode. The problem is defined as follows:

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

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".

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

Clarifying Questions

1. Q: Can the dictionary contain duplicate words?
   • A: Typically, dictionaries do not contain duplicates, but we should handle this case gracefully (e.g., by using a Set).
2. Q: Are all characters in the input string s lowercase letters?
   • A: Yes, according to the problem statement on LeetCode.
3. Q: Can the wordDict be empty?
   • A: Yes, and if it is empty, you should immediately return false unless the string s is also empty.
4. Q: What are the length constraints on s and wordDict?
   • A: The length of s is between 1 and 300, and wordDict can have up to 1,000 words, each with maximum length of 20.

Strategy

The key to solving this problem efficiently is to use Dynamic Programming (DP). Here is the approach:

1. DP Array: Create a boolean array dp where dp[i] represents whether the substring s[0:i] can be segmented into one or more words in the dictionary.
2. Initialization: Set dp[0] = true because an empty string can always be segmented.
3. Iteration: For each position i in s and each position j before i, check if the substring s[j:i] is in the word dictionary and if dp[j] is true.
4. Result: The value of dp[s.length()] will give the answer to the problem.

Code

import java.util.*;

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict); // Convert list to set for O(1) lookup
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true; // Base case: an empty string can be segmented

        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()];
    }
}

Time Complexity

• Time Complexity: O(n^2), where n is the length of the string s. This is because for each position i in the string, we need to check every previous position j.
• Space Complexity: O(n + m), where n is the length of the string s (for the DP array) and m is the size of the word dictionary (for storing words in a set).

This approach ensures that we efficiently check all possible segmentations of the string s using the words in wordDict.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?