Daily LeetCode Problems: Problem 139. Word Break

Breaking It Down: Solving the Word Break Problem

Introduction:

Welcome to another problem-solving article! In today’s edition, we’ll delve into problem 139 from LeetCode, titled “Word Break.” This problem challenges us to determine if a given string can be segmented into a sequence of words from a dictionary. We’ll carefully analyze the problem statement, devise an efficient approach, provide pseudocode for better understanding, explain the core concepts, and discuss the complexity analysis.

Problem Statement:

The problem presents us with a string s and a dictionary wordDict containing various words. Our goal is to determine whether the given string can be divided into a sequence of words from the dictionary. Importantly, the words in the dictionary can be reused multiple times to form the string.

Approach:

To solve this problem, we can use the dynamic programming approach. We’ll iterate through the given string s and check if any prefix of s can be segmented into words from the dictionary. We'll maintain a dynamic programming array to keep track of the segmentation possibilities for different prefixes of s. Specifically, if a prefix of s can be segmented into words from the dictionary, we'll mark that position in the DP array as True.

Pseudocode:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True  # An empty string can always be segmented
        
        wordSet = set(wordDict)  # Convert wordDict to a set for faster lookups
        
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break
        
        return dp[n]

Explanation:

1. We initialize a dynamic programming array dp where dp[i] indicates whether the substring s[:i] can be segmented into words from the dictionary.
2. We mark the base case dp[0] as True because an empty string can always be segmented.
3. We convert wordDict to a set called wordSet for faster lookups.
4. We iterate through the string s from left to right (index i) and check whether any prefix of s (substring s[:i]) can be segmented into words from the dictionary.
5. To do this, we check all possible positions (index j) where we can split the substring s[:i] into two parts: s[:j] and s[j:i].
6. If dp[j] is True (meaning s[:j] can be segmented) and s[j:i] is found in the wordSet, we update dp[i] to True and break the inner loop.
7. Finally, we return the value of dp[n], where n is the length of the string s.

Complexity Analysis:

• Time complexity: The dynamic programming approach iterates through each position in the string s, and for each position, it checks the substrings against the wordSet. Therefore, the time complexity is O(n^2), where n is the length of the input string.
• Space complexity: We use an additional dynamic programming array dp of size n+1 and a wordSet of size k, where k is the number of words in the dictionary. Thus, the space complexity is O(n + k).

Full Solution

Python

class Solution:
  def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    wordSet = set(wordDict)

    @functools.lru_cache(None)
    def wordBreak(s: str) -> bool:
      if s in wordSet:
        return True
      return any(s[:i] in wordSet and wordBreak(s[i:]) for i in range(len(s)))

    return wordBreak(s)

Java

class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return wordBreak(s, new HashSet<>(wordDict), new HashMap<>());
  }

  private boolean wordBreak(final String s, Set<String> wordSet, Map<String, Boolean> memo) {
    if (memo.containsKey(s))
      return memo.get(s);
    if (wordSet.contains(s)) {
      memo.put(s, true);
      return true;
    }

    // 1 <= prefix.length() < s.length()
    for (int i = 1; i < s.length(); ++i) {
      final String prefix = s.substring(0, i);
      final String suffix = s.substring(i);
      if (wordSet.contains(prefix) && wordBreak(suffix, wordSet, memo)) {
        memo.put(s, true);
        return true;
      }
    }

    memo.put(s, false);
    return false;
  }
}

C++

class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    return wordBreak(s, {wordDict.begin(), wordDict.end()}, {});
  }

 private:
  bool wordBreak(const string& s, const unordered_set<string>&& wordSet,
                 unordered_map<string, bool>&& memo) {
    if (wordSet.count(s))
      return true;
    if (const auto it = memo.find(s); it != memo.cend())
      return it->second;

    // 1 <= prefix.length() < s.length()
    for (int i = 1; i < s.length(); ++i) {
      const string& prefix = s.substr(0, i);
      const string& suffix = s.substr(i);
      if (wordSet.count(prefix) && wordBreak(suffix, move(wordSet), move(memo)))
        return memo[s] = true;
    }

    return memo[s] = false;
  }
};

Conclusion:

In this article, we tackled LeetCode problem 139, “Word Break.” We examined the problem statement, devised an efficient dynamic programming approach, provided pseudocode to illustrate the implementation, and discussed the time and space complexities. By leveraging dynamic programming, we efficiently determined whether a given string can be segmented into a sequence of words from a dictionary. Continue practicing similar problems to enhance your algorithmic skills. Stay tuned for more exciting LeetCode challenges in our daily series. Happy coding!