-1

同じ結果が得られる次の 2 つのコードを見てください。

他の誰かの解決策：

bool hasSubstring(const char *word, const char *container) {

    if (container[0] == '\0' || word[0] == '\0')
        return false;

    for(int i = 0; container[i] != '\0'; i++) {

        bool foundNonMatch = false;
        for(int j = 0; word[j] != '\0'; j++) {

            if (container[i + j] != word[j]) {
                foundNonMatch = true;
                break;
            }

        }

        if (!foundNonMatch)
            return true;
    }

    return false;
}

私の解決策：

bool isSubstringOf(string word, string container) {

    bool success = false;       

    // if either is empty, automatically return false 
    if (!word.empty() && !container.empty()) {

        // loop through the container and while not successful
        for (unsigned i = 0; i < container.size() && !success; i++) {

            // if the first letter of the word is found in the container...
            if (word.at(0) == container.at(i)) {                        

                success = true; // success is temporarily true

                // loop through the word to make sure it exists in the container
                for (unsigned j = 1; j < word.size(); j++) {

                    // if either a mismatch happens, or container is too small
                    if (container.size() <= (j+i) || word.at(j) != container.at(j+i)) 
                        success = false;    // set the flag to false again

                }

            }
        }
    }

    return success;
}

時間と複雑さが少ないのはどれですか?

私の知る限り、どちらもO(n^2)最悪ですよね？

4

3 に答える 3

0

どちらも 2 次です。どちらの場合も、コンテナーのすべての文字が各単語のすべての文字に対してチェックされます。
あなたが尋ねたので、

「時間と複雑さ」

一般的には答えられません。お使いのマシンでどれが最も速いかを確認してください。

于 2013-08-01T14:26:34.387 に答える