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 10⁵.

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)) {
            res.add(new ArrayList<>());
            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))) {
                    v.add(0, s.substring(0, i));
                    res.add(v);
                }
            }
        }
        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)
                        {
                            paths[i].Add(Tuple.Create(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)
                {
                    results.Add(sb.ToString());
                }
                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;
    }
}

140 - Word Break II

140. Word Break II

Description

Solutions

Trie Class

Solution Class

All Problems

All Solutions

Welcome to Subscribe On Youtube

140. Word Break II

Description

Solutions

Trie Class

Solution Class

All Problems

All Solutions