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 <= 201 <= wordDict.length <= 10001 <= wordDict[i].length <= 10s 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
Solution 1
PythonJavaGoC#
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 [[]]
res = []
for i in range(1, len(s) + 1):
if trie.search(s[:i]):
for v in dfs(s[i:]):
res.append([s[:i]] + v)
return res
trie = Trie()
for w in wordDict:
trie.insert(w)
ans = dfs(s)
return [' '.join(v) for v in ans](code-box)
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;
}
}(code-box)
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
}(code-box)
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;
}
}(code-box)
