题目

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

  1. Input:
  2. s = "catsanddog"
  3. wordDict = ["cat", "cats", "and", "sand", "dog"]
  4. Output:
  5. [
  6.   "cats and dog",
  7.   "cat sand dog"
  8. ]

Example 2:

  1. Input:
  2. s = "pineapplepenapple"
  3. wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
  4. Output:
  5. [
  6.   "pine apple pen apple",
  7.   "pineapple pen apple",
  8.   "pine applepen apple"
  9. ]
  10. Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

  1. Input:
  2. s = "catsandog"
  3. wordDict = ["cats", "dog", "sand", "and", "cat"]
  4. Output:
  5. []

题意

判断给定字符串按照某种方式分割后得到的所有子串能否在给定数组中找到，并返回所有可能的分割方式。

思路

139. Word Break (M) 威力加强版。使用记忆化DFS搜索处理。在139题的基础上进行改动：HashMap记录字符串s中以下标start为起点的子字符串的所有分割方式(如果无法有效分割则为空)。

代码实现

Java

  1. class Solution {
  2.     Map<Integer, List<String>> hash = new HashMap<>();
  4.     public List<String> wordBreak(String s, List<String> wordDict) {
  5.         return dfs(s, 0, wordDict);
  6.     }
  8.     private List<String> dfs(String s, int start, List<String> wordDict) {
  9.         if (hash.containsKey(start)) {
  10.             return hash.get(start);
  11.         }
  13.         List<String> res = new ArrayList<>();
  15.         // 边界处理，说明这种分割方式有效，添加空字符串方便处理
  16.         if (start == s.length()) {
  17.             res.add("");
  18.             return res;
  19.         }
  21.         for (String word : wordDict) {
  22.             // 每次先找到下一个能有效分割的位置
  23.             if (s.substring(start).startsWith(word)) {
  24.                 List<String> next = dfs(s, start + word.length(), wordDict);
  25.                 for (String t : next) {
  26.                     // 注意空格的处理
  27.                     if (!t.isEmpty()) {
  28.                         t = " " + t;
  29.                     }
  30.                     res.add(word + t);
  31.                 }
  32.             }
  33.         }
  35.         // 如果以start为起点的子串不能有效分割，则返回的res是一个空list
  36.         hash.put(start, res);
  37.         return res;    
  38.     }
  39. }

JavaScript

  1. /**
  2.  * @param {string} s
  3.  * @param {string[]} wordDict
  4.  * @return {string[]}
  5.  */
  6. var wordBreak = function (s, wordDict) {
  7.   return dfs(s, 0, new Map([[s.length, [[]]]]), wordDict).map(v => v.join(' '))
  8. }
  10. let dfs = function (s, index, record, wordDict) {
  11.   if (record.has(index)) {
  12.     return record.get(index)
  13.   }
  15.   let lists = []
  16.   for (let word of wordDict) {
  17.     if (s.slice(index).startsWith(word)) {
  18.       let next = dfs(s, index + word.length, record, wordDict)
  19.       for (let list of next) {
  20.         let tmp = [...list]
  21.         tmp.unshift(word)
  22.         lists.push(tmp)
  23.       }
  24.     }
  25.   }
  27.   record.set(index, lists)
  28.   return lists
  29. }