前言
持续更新了
正文
问题来源
本问题来自leetcode上的140题。
问题描述
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。
说明：
分隔时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1:
输入:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
输出:
[
"cats and dog",
"cat sand dog"
]
示例 2:
输入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
输出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解释: 注意你可以重复使用字典中的单词。
示例 3:
输入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
输出:
[]
分析：
最直观的想法，暴力求解
func wordBreak(s string, wordDict []string) []string {
res := make([]string, 0)
dfs([]byte(s), wordDict, "", &res)
return res
}
func dfs(s []byte, wordDict []string, cur string, res *[]string) {
if len(s) == 0 {
*res = append(*res, string(cur[1:]))
}
for _, v := range wordDict {
if strings.HasPrefix(string(s), v) {
dfs(s[len(v):], wordDict, cur+" "+v, res)
}
}
}
但是提交之后效率不行
然后看官方题解修改暴力求解，改为有记忆的暴力求解
var m map[int][]string
func wordBreak(s string, wordDict []string) []string {
m = make(map[int][]string)
return dfs([]byte(s), wordDict, 0)
}
func dfs(s []byte, wordDict []string, start int) []string{
if v, ok := m[start]; ok {
return v
}
res := make([]string, 0)
if len(s) == 0 {
res = append(res, "")
}
for _, v := range wordDict {
if strings.HasPrefix(string(s), v) {
list := dfs(s[len(v):], wordDict, start+len(v))
for _, lv := range list {
if lv == "" {
res = append(res, v)
} else {
res = append(res, v+" "+lv)
}
}
}
}
m[start] = res
return res
}
官方解答中提供了动态规划的解法，然后我按照该思想实现了golang版本的算法
func wordBreak(s string, wordDict []string) []string {
dp := make([][]string, len(s)+1)
dp[0] = []string{""}
for i := 1; i <= len(s); i++ {
dp[i] = make([]string, 0)
for j := 0; j < i; j++ {
for _, v := range wordDict {
if string(s[j:i]) == v {
list := dp[i-len(v)]
for _, lv := range list {
if lv == "" {
dp[i] = append(dp[i], v)
} else {
dp[i] = append(dp[i], lv+" "+v)
}
}
}
}
}
}
return dp[len(s)]
}
然而超时了，这道题和恢复空格那题很像，我们可以用trie树来优化。
type Trie struct {
Next []*Trie
End bool
}
func NewTrie() *Trie {
return &Trie {
Next : make([]*Trie, 26),
End : false,
}
}
func (t *Trie) Insert(s string) {
cur := t
for i := len(s)-1; i >= 0; i-- {
j := s[i] - 'a'
if cur.Next[j] == nil {
cur.Next[j] = NewTrie()
}
cur = cur.Next[j]
}
cur.End = true
}
func wordBreak(s string, wordDict []string) []string {
root := NewTrie()
for _, v := range wordDict {
root.Insert(v)
}
dp := make([][]string, len(s)+1)
dp[0] = []string{""}
for i := 1; i <= len(s); i++ {
dp[i] = make([]string, 0)
cur := root
for j := i; j > 0; j-- {
t := s[j-1] - 'a'
if cur.Next[t] == nil {
break
} else if cur.Next[t].End {
list := dp[j-1]
for _, lv := range list {
if lv == "" {
dp[i] = append(dp[i], string(s[j-1:i]))
} else {
dp[i] = append(dp[i], lv+" "+string(s[j-1:i]))
}
}
}
cur = cur.Next[t]
}
}
return dp[len(s)]
}
然而还是超时
这个c++的动态规划可以跑完,也不知道差在哪里
class Solution {
public:
vector<string> wordBreak(string s, vector<string>& wordDict)
{
if (!wordBreak_139(s, wordDict)) return {};
size_t validEnd = 0;
vector<vector<string>> dp(s.size() + 1, vector<string>());
for (size_t i = 0; i < s.size(); i++)
{
if (i == validEnd + 1) return {};
if (i != 0 && dp[i].empty()) continue;
for (auto& word : wordDict)
{
size_t newEnd = i + word.size();
if (newEnd > s.size()) continue;
if (memcmp(&s[i], &word[0], word.size()) != 0) continue;
validEnd = max(validEnd, newEnd);
if (i == 0)
{
dp[newEnd].push_back(word);
continue;
}
for (auto& d : dp[i])
{
dp[newEnd].push_back(d + " " + word);
}
}
}
return dp.back();
}
bool wordBreak_139(string& s, vector<string>& wordDict)
{
size_t validEnd = 0;
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (size_t i = 0; i < s.size(); i++)
{
if (i == validEnd + 1) return false;
if (!dp[i]) continue;
for (auto& word : wordDict)
{
size_t newEnd = i + word.size();
if (newEnd > s.size()) continue;
if (memcmp(&s[i], &word[0], word.size()) == 0)
{
dp[newEnd] = true;
validEnd = max(validEnd, newEnd);
}
}
}
return dp.back();
}
};
总结：
勤思考。
结语
不管怎么样好好加油。
