Question

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

Solution 1

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]

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;
  }
}

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;
  }
}