2

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

例如，给定 s = "hithere", dict = ["hi", "there"]。

返回 true 因为“hithere”可以被分割为“leet code”。

我的实现如下。此代码适用于正常情况。但是，它会遭受很多输入，例如：

s = “aaaaaaaaaaaaaaaaaaaaab”，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;
    }
};
4

4 回答 4

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 和一堆边。但是节点 23b完全无法访问——没有传入边缘。现在这是一个简单的图论问题

如果你的字典被组织成一个 trie，那么查找字典单词出现的所有地方非常容易。std::map但由于它的equal_range方法，即使是 an也是可用的。对于开始和结束位置，您似乎有一个 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。由于不存在，您立即知道该节点{23}是孤立的。

于 2015-05-12T15:08:34.270 回答
0

在您的代码中，您没有使用动态编程，因为您不记得已经解决的子问题。

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

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

于 2015-05-12T14:09:50.093 回答
0

尝试以下操作：

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;
    }
};

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

于 2015-05-12T14:14:51.043 回答
0

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

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

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;
    }
};
于 2015-05-12T16:32:01.050 回答