Word Break II (H)
題目
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:
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:
[]
題意
判斷給定字串按照某種方式分割后得到的所有子串能否在給定陣列中找到，并回傳所有可能的分割方式，
思路
- Word Break 威力加強版，使用記憶化DFS搜索處理，在139題的基礎上進行改動：HashMap記錄字串s中以下標start為起點的子字串的所有分割方式(如果無法有效分割則為空)，
代碼實作
Java
class Solution {
Map<Integer, List<String>> hash = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
return dfs(s, 0, wordDict);
}
private List<String> dfs(String s, int start, List<String> wordDict) {
if (hash.containsKey(start)) {
return hash.get(start);
}
List<String> res = new ArrayList<>();
// 邊界處理，說明這種分割方式有效，添加空字串方便處理
if (start == s.length()) {
res.add("");
return res;
}
for (String word : wordDict) {
// 每次先找到下一個能有效分割的位置
if (s.substring(start).startsWith(word)) {
List<String> next = dfs(s, start + word.length(), wordDict);
for (String t : next) {
// 注意空格的處理
if (!t.isEmpty()) {
t = " " + t;
}
res.add(word + t);
}
}
}
// 如果以start為起點的子串不能有效分割，則回傳的res是一個空list
hash.put(start, res);
return res;
}
}
JavaScript
/**
* @param {string} s
* @param {string[]} wordDict
* @return {string[]}
*/
var wordBreak = function (s, wordDict) {
return dfs(s, 0, new Map([[s.length, [[]]]]), wordDict).map(v => v.join(' '))
}
let dfs = function (s, index, record, wordDict) {
if (record.has(index)) {
return record.get(index)
}
let lists = []
for (let word of wordDict) {
if (s.slice(index).startsWith(word)) {
let next = dfs(s, index + word.length, record, wordDict)
for (let list of next) {
let tmp = [...list]
tmp.unshift(word)
lists.push(tmp)
}
}
}
record.set(index, lists)
return lists
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10657.html
標籤：其他