-2

leetcode 139、単語区切りをしていたときに問題が発生しました。

文字列 s と単語辞書 dict を指定して、s を 1 つ以上の辞書単語のスペース区切りのシーケンスに分割できるかどうかを判断します。（各辞書の単語は複数回使用できます。）

たとえば、指定された s = "leetcode", dict = ["leet", "code"].

「leetcode」は「leet code」として分割できるため、true を返します。

基本的な動的計画法アルゴリズムを使用しますが、インターネットで一般的なものとは異なる方法で実装する場合があります。コードは次のとおりです。

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"]"、私のコードは true を出力し、予想される答えは false です。ただし、オンライン テストで実行すると、正しい出力が得られます。また、clang ++ を使用した自分の仮想マシンでも問題なく動作します。

オンラインジャッジとオンラインテストの違いは、各オンラインテストは 1 つのテストのみであるということです。オンラインジャッジには多くのテストが含まれており、いずれかのテストが失敗すると失敗します。したがって、私のコードの問題は次のようになる可能性があります。「aaaaaaa」以外のテストでは、正しい出力が得られますが、潜在的な問題が発生します。そして、それが私のコードが「aaaaaaa」で失敗する理由です。ただし、この 1 つのテストを実行するだけであれば問題ありません。

leetcode の Web サイトによると、コードに未定義の動作が含まれている可能性があります。前のテスト ケースが後者のテスト ケースに影響を与える可能性があります。以前のすべてのテスト ケースが何であるかはわかりませんし、ここにいる誰もそれについて知っているとは思っていませんでした。しかし、私のコードに問題がある限り、誰かがそれを見つけることができると思います.

今回の質問はかなり明確だと思います。

4

1 に答える 1

1

この行パラメーターの順序が間違っていますvector<bool> sepable(false, strlen);。vector<bool> sepable(strlen,false);ベクトルの長さが最初に来て、次にデフォルト値であり、 false が暗黙的に int に変換されるため、長さが 0 に設定され、未定義の動作が発生します。

于 2016-01-07T15:09:08.693 に答える