需要提高断字速度的建议（动态规划）

Question

问题是：给定一个字符串 s 和一个单词字典 dict，确定 s 是否可以被分割成 space 分隔的一个或多个字典单词序列。

例如，给定小号 = "hithere", 字典 = ["hi", "there"].

Return 正确，因为 "hithere" 可以分割为 "leet code"。

我的实现如下。此代码适用于正常情况。然而，它对像这样的输入有很多影响：

s = "aaaaaaaaaaaaaaaaaaaaaaab", dict = {"aa", "aaaaaa", "aaaaaaaa"}.

我想记住处理后的子字符串，但是我做不对。关于如何改进的任何建议？非常感谢！

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.size();
        if(len<1) return true;
        for(int i(0); i<len; i++) {
            string tmp = s.substr(0, i+1);
            if((wordDict.find(tmp)!=wordDict.end()) 
               && (wordBreak(s.substr(i+1), wordDict)) )
                return true;
        }
        return false;
    }
};

Answer 1

在你的代码中，你没有使用动态规划，因为你没有记住你已经解决的子问题。

您可以启用此记忆功能，例如，根据字符串 s 在原始字符串中的起始位置存储结果，甚至根据其长度存储结果（因为无论如何您正在处理的字符串with 是原始字符串的后缀，因此它的长度唯一地标识了它）。然后，在你的 wordBreak 函数的开头，只检查是否已经处理了这样的长度，如果已经处理，不要重新运行计算，只是 return 存储的值。否则，运行次计算并存储结果。

另请注意，您使用 unordered_set 的方法不会让您获得最快的解决方案。我能想到的最快的解决方案是 O(N^2)，方法是将所有单词存储在一个特里树中（而不是在地图中！），并在您沿着给定的字符串遍历时遵循这个特里树。这实现了 O(1) 每次循环迭代不计算递归调用。

Answer 2

尝试以下操作：

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) 
    {
        for (auto w : wordDict)
        {
            auto pos = s.find(w);
            if (pos != string::npos)
            {
                if (wordBreak(s.substr(0, pos), wordDict) && 
                    wordBreak(s.substr(pos + w.size()), wordDict))
                    return true;
            }
        }
        return false;
    }
};

基本上，您找到一个匹配项会从输入字符串中删除匹配部分，然后继续在较小的输入上进行测试。

Answer 3

这在逻辑上是一个两步过程。查找输入中的所有字典单词，考虑找到的位置（begin/end 对），然后查看这些单词是否覆盖整个输入。

所以你会得到你的例子

aa:       {0,2}, {1,3}, {2,4}, ... {20,22}
aaaaaa:   {0,6}, {1,7}, ... {16,22}
aaaaaaaa: {0,8}, {1,9} ... {14,22}

这是一个图，有节点 0-23 和一堆边。但是节点 23 b 完全无法访问 - 没有传入边。这是一个简单的图论问题

如果您的字典是按 trie 树组织的，则查找字典单词出现的所有位置非常容易。但由于其 equal_range 方法，即使 std::map 也可用。对于开始和结束位置，您似乎有一个 O(N*N) 嵌套循环，每个单词都有 O(log N) 查找。但是您可以快速确定 s.substr(begin,end) 是否仍然是一个可行的前缀，以及该前缀保留了哪些词典单词。

另请注意，您可以延迟构建图表。盯着 begin=0 你会发现边缘 {0,2}, {0,6} and {0,8}。（没有其他人）。您现在可以搜索节点 2、6 和 8。您甚至有一个很好的算法 - A* - 建议您首先尝试节点 8（仅在 1 个边缘可到达）。因此，您将找到节点 {8,10}、{8,14} 和 {8,16} 等。如您所见，您永远不需要构建包含 {1,3} 的图形部分简直是遥不可及。

使用图论，很容易看出您的蛮力方法失败的原因。您反复到达节点 8 (aaaaaaaa.aaaaaaaaaaaaaab)，并且每次都从那里开始搜索子图。

进一步的优化是运行双向 A*。这会给你一个非常快速的解决方案。在第一步的后半部分，您寻找通向 23, b 的边。由于 none 存在，您立即知道节点 {23} 是孤立的。

Answer 4

感谢所有评论。我将以前的解决方案更改为下面的实现。在这一点上，我没有探索优化字典，但这些见解非常有价值，非常感谢。

对于目前的实现方式，您认为还可以进一步改进吗？谢谢！

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int len = s.size();
        if(len<1) return true;
        if(wordDict.size()==0) return false;

        vector<bool> dq (len+1,false);
        dq[0] = true;
        for(int i(0); i<len; i++) {// start point
            if(dq[i]) {
                for(int j(1); j<=len-i; j++) {// length of substring, 1:len
                    if(!dq[i+j]) {
                        auto pos = wordDict.find(s.substr(i, j));
                        dq[i+j] = dq[i+j] || (pos!=wordDict.end());
                    }
                }
            }
            if(dq[len]) return true;
        }
        return false;
    }
};

需要提高断字速度的建议（动态规划）

Need suggestion to improve speed for word break (dynamic programming)

c++

dynamic-programming

word-break