LeetCode Hard – 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 10⁵.

Java Solution

To solve this problem, you can use backtracking to generate all possible sentences by trying different word combinations. Here’s a Java solution:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WordBreakII {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Map<String, List<String>> memo = new HashMap<>();
        return wordBreakHelper(s, new HashSet<>(wordDict), memo);
    }

    private List<String> wordBreakHelper(String s, Set<String> wordDict, Map<String, List<String>> memo) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }

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

        if (wordDict.contains(s)) {
            result.add(s);
        }

        for (int i = 1; i < s.length(); i++) {
            String prefix = s.substring(0, i);
            if (wordDict.contains(prefix)) {
                String suffix = s.substring(i);
                List<String> suffixList = wordBreakHelper(suffix, wordDict, memo);
                for (String word : suffixList) {
                    result.add(prefix + " " + word);
                }
            }
        }

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

    public static void main(String[] args) {
        WordBreakII solution = new WordBreakII();

        // Example 1
        String s1 = "catsanddog";
        List<String> wordDict1 = List.of("cat", "cats", "and", "sand", "dog");
        System.out.println(solution.wordBreak(s1, wordDict1));

        // Example 2
        String s2 = "pineapplepenapple";
        List<String> wordDict2 = List.of("apple", "pen", "applepen", "pine", "pineapple");
        System.out.println(solution.wordBreak(s2, wordDict2));

        // Example 3
        String s3 = "catsandog";
        List<String> wordDict3 = List.of("cats", "dog", "sand", "and", "cat");
        System.out.println(solution.wordBreak(s3, wordDict3));
    }
}

This Java code defines a WordBreakII class with the wordBreak method, which uses backtracking to generate all possible sentences. The provided test cases demonstrate its usage.

Python Solution

Here’s the equivalent Python solution for the Word Break II problem using backtracking:

from typing import List

class WordBreakII:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        memo = {}
        wordSet = set(wordDict)
        return self.wordBreakHelper(s, wordSet, memo)

    def wordBreakHelper(self, s: str, wordDict: set, memo: dict) -> List[str]:
        if s in memo:
            return memo[s]

        result = []

        if s in wordDict:
            result.append(s)

        for i in range(1, len(s)):
            prefix = s[:i]
            if prefix in wordDict:
                suffix = s[i:]
                suffixList = self.wordBreakHelper(suffix, wordDict, memo)
                for word in suffixList:
                    result.append(prefix + " " + word)

        memo[s] = result
        return result

# Test cases
solution = WordBreakII()

# Example 1
s1 = "catsanddog"
wordDict1 = ["cat", "cats", "and", "sand", "dog"]
print(solution.wordBreak(s1, wordDict1))

# Example 2
s2 = "pineapplepenapple"
wordDict2 = ["apple", "pen", "applepen", "pine", "pineapple"]
print(solution.wordBreak(s2, wordDict2))

# Example 3
s3 = "catsandog"
wordDict3 = ["cats", "dog", "sand", "and", "cat"]
print(solution.wordBreak(s3, wordDict3))

This Python code defines a WordBreakII class with the wordBreak method, which uses backtracking to generate all possible sentences. The provided test cases demonstrate its usage.