时间戳

首页 > 解决方案 > 如何找到在单个字典单词中剪切句子的方法总数

algorithm - 如何找到在单个字典单词中剪切句子的方法总数

问题描述

我面临着优化一个问题的解决方案，它是word break II的一个变体。

但是在这个问题中，我必须找到句子的总数而不打印它们。所以不想存储它们。

我写了一个蛮力解决方案，我将所有有效的句子保存在一个容器中，然后最终返回它的总大小。

这是我写的代码

unordered_set<string> getWays(string str, unordered_set<string> &wordDict) {
    unordered_set<string> ans;
    if(str.empty()) {
        return ans;
    }
    if(wordDict.find(str) != wordDict.end()) {
        ans.insert(str);
    }
    for(int i = 1; i <= str.size(); i++) {
        string pre = str.substr(0, i);
        string suf = str.substr(i);
        if(wordDict.find(pre) != wordDict.end()) {
            unordered_set<string> ans_for_suf = getWays(suf, wordDict);
            for(string s : ans_for_suf) {
                ans.insert(pre + "|" + s);
            }
        }
    }
    return ans;
}

and I am using ans.size() as the answer.

在这里我可以使用动态编程来进一步优化它，但这不是一个好方法。

所以我的目标是假设输入是

s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]

然后没有返回

[
  "cats and dog",
  "cat sand dog"
]

我想返回2，也就是上面返回数组的大小。

请给我一些想法。

标签： algorithmdata-structures

解决方案

这是使用Trie和DFS的解决方案：

  • 使用字典中的所有单词构建一个 trie。
  • 从给定的字符串开始一个 dfs 。每个字符都是一个节点。
  • 遍历给定的字符串，并检查您当前是否处于任何字典单词结束的位置。
  • 如果有一个字典词以这里结尾，则从那里开始 dfs 。

这个简单的递归解决方案会起作用，但不会及时。使用dp 记忆，它应该是有效的。

推荐阅读