c++ - 需要提高断字速度的建议(动态规划)

Question

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

例如，给定 s = "那里", dict = ["hi", "there"].

返回 true 因为“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

这在逻辑上是一个两步过程。查找输入中的所有字典单词，考虑找到的位置(开始/结束对)，然后查看这些单词是否覆盖了整个输入。

所以你会得到你的例子

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

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

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

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