-2

我在做 leetcode 139 的时候遇到了一个问题，分词。

给定一个字符串 s 和一个单词字典 dict，确定 s 是否可以分割成一个或多个字典单词的空格分隔序列。（每个字典单词可以多次使用。）

例如，给定 s = "leetcode", dict = ["leet", "code"]。

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

我使用基本的动态规划算法，但可能以与互联网上流行的不同的方式实现它。这是代码：

class Solution {
public:
    bool wordBreak(string s, unordered_set<string>& wordDict) {
        int strlen = s.length();
        if(0 == strlen)  return true;
        vector<bool> sepable(false, strlen);
        for(int i = 0; i < strlen; ++i) {
            if(wordDict.count(s.substr(0,i+1)) > 0) {
                sepable[i] = true;
                continue;
            }
            for(int j = 0; j < i; ++j) {
                if(sepable[j] && wordDict.count(s.substr(j+1,i-j)) > 0) {
                    sepable[i] = true;
                    break;
                }
            }
        }
        return sepable[strlen-1];
    }
};

当我运行在线判断时，它在测试中失败：““aaaaaaa”[“aaaa”，“aa”]”，我的代码输出为真，预期答案为假。但是，如果我在在线测试中运行它，它会给出正确的输出。此外，它在我自己的带有 clang++ 的虚拟机上运行良好。

在线评委和在线测试的区别在于，每个在线测试只有一个测试。在线法官包含许多测试，如果任何一个测试失败，就会失败。所以我的代码的问题可能是这样的：在“aaaaaaa”以外的一些测试中，它给出了正确的输出，但会导致一些潜在的问题。这就是为什么我的代码会在“aaaaaaa”上失败。但是，如果我只运行这个单一的测试，那就没问题了。

leetcode 网站说这可能是因为我的代码有一些未定义的行为。前一个测试用例可能会影响后一个测试用例。我不知道以前的所有测试用例是什么，没想到这里有人知道。但我觉得只要我的代码有问题，总有人能找到的。

我认为这次的问题很清楚。

4

1 回答 1

1

此行参数的顺序错误vector<bool> sepable(false, strlen);它应该是vector<bool> sepable(strlen,false);向量的长度，然后是默认值，并且 false 被隐式转换为 int 所以长度设置为 0 给出未定义的行为

于 2016-01-07T15:09:08.693 回答