140. Word Break II LeetCode Solution

Last updated: February 14, 2025

In this guide, you will get 140. Word Break II LeetCode Solution with the best time and space complexity. The solution to Word Break II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Word Break II solution in C++
Word Break II solution in Java
Word Break II solution in Python
Additional Resources

140. Word Break II LeetCode Solution image

Problem Statement of Word Break II

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.
Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]
Output: [“cats and dog”,”cat sand dog”]

Example 2:

Input: s = “pineapplepenapple”, wordDict = [“apple”,”pen”,”applepen”,”pine”,”pineapple”]
Output: [“pine apple pen apple”,”pineapple pen apple”,”pine applepen apple”]
Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]
Output: []

Constraints:

1 <= s.length <= 20
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 10
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.
Input is generated in a way that the length of the answer doesn't exceed 105.

Complexity Analysis

Time Complexity: O(2^n)
Space Complexity: O(2^n)

140. Word Break II LeetCode Solution in C++

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

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

    vector<string> ans;

    // 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.contains(prefix))
        for (const string& word : wordBreak(suffix, wordSet, mem))
          ans.push_back(prefix + " " + word);
    }

    // `wordSet` contains the whole string s, so don't add any space.
    if (wordSet.contains(s))
      ans.push_back(s);

    return mem[s] = ans;
  }
};
/* code provided by PROGIEZ */

140. Word Break II LeetCode Solution in Java

class Solution {
  public List<String> wordBreak(String s, List<String> wordDict) {
    Set<String> wordSet = new HashSet<>(wordDict);
    Map<String, List<String>> mem = new HashMap<>();
    return wordBreak(s, wordSet, mem);
  }

  private List<String> wordBreak(final String s, Set<String> wordSet,
                                 Map<String, List<String>> mem) {
    if (mem.containsKey(s))
      return mem.get(s);

    List<String> ans = new ArrayList<>();

    // 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))
        for (final String word : wordBreak(suffix, wordSet, mem))
          ans.add(prefix + " " + word);
    }

    // `wordSet` contains the whole string s, so don't add any space.
    if (wordSet.contains(s))
      ans.add(s);

    mem.put(s, ans);
    return ans;
  }
}
// code provided by PROGIEZ

140. Word Break II LeetCode Solution in Python

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

    @functools.lru_cache(None)
    def wordBreak(s: str) -> list[str]:
      ans = []

      # 1 <= len(prefix) < len(s)
      for i in range(1, len(s)):
        prefix = s[0:i]
        suffix = s[i:]
        if prefix in wordSet:
          for word in wordBreak(suffix):
            ans.append(prefix + ' ' + word)

      # `wordSet` contains the whole string s, so don't add any space.
      if s in wordSet:
        ans.append(s)

      return ans

    return wordBreak(s)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents