Word Break II Leetcode Solution

Hello Programmers, In this post you will know how 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 Solutions

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.


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.

Word Break II Leetcode Solutions 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 Solutions 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 Solutions 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 BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: Word Break Leetcode Solution

Leave a Reply

Your email address will not be published. Required fields are marked *