Word Break II Leetcode Solution

In this post, we are going to solve the Word Break II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Word Break II Leetcode Solution
Word Break II Leetcode Solution


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: []


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

Now, lets see the leetcode solution of Word Break II Leetcode Solution.

Word Break II Leetcode Solution in Python

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

    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)

      # Contains whole string, so don't add any space
      if s in wordSet:

      return ans

    return wordBreak(s)

Word Break II Leetcode Solution in CPP

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

  vector<string> wordBreak(const string& s,
                           const unordered_set<string>& wordSet,
                           unordered_map<string, vector<string>>& memo) {
    if (memo.count(s))
      return memo[s];

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

    // Contains whole string, so don't add any space
    if (wordSet.count(s))

    return memo[s] = ans;

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>> memo = new HashMap<>();
    return wordBreak(s, wordSet, memo);

  private List<String> wordBreak(final String s, Set<String> wordSet,
                                 Map<String, List<String>> memo) {
    if (memo.containsKey(s))
      return memo.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, memo))
          ans.add(prefix + " " + word);

    // Contains whole string, so don't add any space
    if (wordSet.contains(s))

    memo.put(s, ans);
    return ans;

Note: This problem Word Break II is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purpose.

Sharing Is Caring

Leave a Comment