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 SolutionsOne 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.ProblemGiven 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 <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s and wordDict[i] consist of only lowercase English letters.All the strings of wordDict are unique.Word Break II Leetcode Solutions in Pythonclass 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) # Contains whole string, so don't add any space if s in wordSet: ans.append(s) return ans return wordBreak(s)Word Break II Leetcode Solutions in CPPclass Solution { public: 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); } private: 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)) ans.push_back(s); return memo[s] = ans; } };Word Break II Leetcode Solutions in Javaclass 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)) ans.add(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 Post navigationBest Time to Buy and Sell Stock III Leetcode Solution Word Break Leetcode Solution