# 140. Word Break II

## Description

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.

## Solutions

Using a Trie and Depth-First Search (DFS). The goal is to determine how a given string s can be segmented into a space-separated sequence of one or more dictionary words from a given list wordDict.

### Trie Class

• Initialization: The Trie node (Trie) is initialized with 26 children (assuming only lowercase letters) and a boolean flag is_end to mark the end of a word.

• Insert Method: Inserts a word into the Trie. For each character in the word, it calculates the index (idx) corresponding to the character’s position in the alphabet. If the child at that index doesn’t exist, it creates a new Trie node. It then moves to this child node. After inserting the last character of the word, it marks is_end as True to indicate the end of the word.

• Search Method: Searches for a word in the Trie. Similar to insertion, it calculates the index for each character. If at any point the expected child node is None, it means the word doesn’t exist in the Trie, and it returns False. If it successfully traverses the word in the Trie, it checks is_end of the last node to confirm the word’s presence.

### Solution Class

• Word Break Function: This is the main function that utilizes a Trie to solve the word break problem. It first inserts all words from wordDict into the Trie for efficient word lookup. Then it uses a DFS approach to find all possible word combinations that can form the given string s.

• DFS Function: A helper function that takes a substring of s as input. If the input is empty, it returns a list containing an empty list, representing a successful path. For each possible prefix of the input substring, it checks if the prefix exists in the Trie. If so, it recursively calls itself with the remaining substring. For each result from the recursive call, it appends the current prefix to the front, forming a new path. These paths are accumulated in res.

• Result Construction: After computing all valid paths that break s into words from wordDict, the dfs function returns a list of lists, where each inner list represents a valid word sequence. The main function then joins these words with spaces to form complete sentences and returns them.

This solution efficiently finds all ways to segment s into a sequence of dictionary words, leveraging the Trie for fast word lookups and DFS for exhaustive search.

• class Trie {
Trie[] children = new Trie[26];
boolean isEnd;

void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
node.children[c] = new Trie();
}
node = node.children[c];
}
node.isEnd = true;
}

boolean search(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
c -= 'a';
if (node.children[c] == null) {
return false;
}
node = node.children[c];
}
return node.isEnd;
}
}

class Solution {
private Trie trie = new Trie();

public List<String> wordBreak(String s, List<String> wordDict) {
for (String w : wordDict) {
trie.insert(w);
}
List<List<String>> res = dfs(s);
return res.stream().map(e -> String.join(" ", e)).collect(Collectors.toList());
}

private List<List<String>> dfs(String s) {
List<List<String>> res = new ArrayList<>();
if ("".equals(s)) {
return res;
}
for (int i = 1; i <= s.length(); ++i) {
if (trie.search(s.substring(0, i))) {
for (List<String> v : dfs(s.substring(i))) {
}
}
}
return res;
}
}

• class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False

def insert(self, word):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True

def search(self, word):
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return False
node = node.children[idx]
return node.is_end

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
def dfs(s):
if not s:
return [[]] # list of list
res = []
for i in range(1, len(s) + 1): # starts from 1, i is excluded in s[:i]
if trie.search(s[:i]):
# if below dfs() returns empty, then returned res also empty
for v in dfs(s[i:]):
res.append([s[:i]] + v) # [1] + [2,3] ==> [1, 2, 3]
return res

trie = Trie()
for w in wordDict:
trie.insert(w)
ans = dfs(s)
return [' '.join(v) for v in ans]

#############

class Solution:
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
res = []
if not self.check_word_break(s, wordDict):
return res

queue = [(0, "")]
slen = len(s)
len_list = set(len(w) for w in wordDict)

while queue:
tmp_queue = []
for q in queue:
start, path = q
for l in len_list:
if start + l <= slen and s[start:start + l] in wordDict:
new_node = (start + l, path + " " + s[start:start + l] if path else s[start:start + l])
tmp_queue.append(new_node)
if start + l == slen:
res.append(new_node[1])
queue = tmp_queue

return res

def check_word_break(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: bool
"""
queue = [0]
slen = len(s)
len_list = set(len(w) for w in wordDict)
visited = [0 for _ in range(slen + 1)]

while queue:
tmp_queue = []
for start in queue:
for l in len_list:
if s[start:start + l] in wordDict:
if start + l == slen:
return True
if not visited[start + l]:
tmp_queue.append(start + l)
visited[start + l] = 1
queue = tmp_queue

• type Trie struct {
children [26]*Trie
isEnd    bool
}

func newTrie() *Trie {
return &Trie{}
}
func (this *Trie) insert(word string) {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
node.children[c] = newTrie()
}
node = node.children[c]
}
node.isEnd = true
}
func (this *Trie) search(word string) bool {
node := this
for _, c := range word {
c -= 'a'
if node.children[c] == nil {
return false
}
node = node.children[c]
}
return node.isEnd
}

func wordBreak(s string, wordDict []string) []string {
trie := newTrie()
for _, w := range wordDict {
trie.insert(w)
}
var dfs func(string) [][]string
dfs = func(s string) [][]string {
res := [][]string{}
if len(s) == 0 {
res = append(res, []string{})
return res
}
for i := 1; i <= len(s); i++ {
if trie.search(s[:i]) {
for _, v := range dfs(s[i:]) {
v = append([]string{s[:i]}, v...)
res = append(res, v)
}
}
}
return res
}
res := dfs(s)
ans := []string{}
for _, v := range res {
ans = append(ans, strings.Join(v, " "))
}
return ans
}

• using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Node
{
public int Index1 { get; set; }
public int Index2 { get; set; }
}

public class Solution {
public IList<string> WordBreak(string s, IList<string> wordDict) {
var paths = new List<Tuple<int, string>>[s.Length + 1];
paths[s.Length] = new List<Tuple<int, string>> { Tuple.Create(-1, (string)null) };
var wordDictGroup = wordDict.GroupBy(word => word.Length);
for (var i = s.Length - 1; i >= 0; --i)
{
paths[i] = new List<Tuple<int, string>>();
foreach (var wordGroup in wordDictGroup)
{
var wordLength = wordGroup.Key;
if (i + wordLength <= s.Length && paths[i + wordLength].Count > 0)
{
foreach (var word in wordGroup)
{
if (s.Substring(i, wordLength) == word)
{
}
}
}
}
}

return GenerateResults(paths);
}

private IList<string> GenerateResults(List<Tuple<int, string>>[] paths)
{
var results = new List<string>();
var sb = new StringBuilder();
var stack = new Stack<Node>();
stack.Push(new Node());
while (stack.Count > 0)
{
var node = stack.Peek();
if (node.Index1 == paths.Length - 1 || node.Index2 == paths[node.Index1].Count)
{
if (node.Index1 == paths.Length - 1)
{
}
stack.Pop();
if (stack.Count > 0)
{
var parent = stack.Peek();
var length = paths[parent.Index1][parent.Index2 - 1].Item2.Length;
if (length < sb.Length) ++length;
sb.Remove(sb.Length - length, length);
}
}
else
{
var newNode = new Node { Index1 = paths[node.Index1][node.Index2].Item1, Index2 = 0 };
if (sb.Length != 0)
{
sb.Append(' ');
}
sb.Append(paths[node.Index1][node.Index2].Item2);
stack.Push(newNode);
++node.Index2;
}
}
return results;
}
}