-1

您能否看看这两条实现相同结果的代码：

别人的解决方案：

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

1

或者，与其重新发明轮子，不如使用：

container.find(word)

它来自标准库，因此您可以确信它具有合理的性能和正确性。您通过使用经过充分测试的已知构建块而不是滚动您自己的构建块来优化程序员时间、QA 时间、用户时间（不发送潜在的错误代码）。

于 2013-08-01T14:30:21.703 回答
0

它们都是二次的——在这两种情况下，容器的每个字母都会与每个单词的每个字母进行检查。
既然你问

“时间和复杂性”

这不能笼统地回答。看看你的机器上哪个最快。

于 2013-08-01T14:26:34.387 回答
0

除非有明显的减速，否则仅通过查看两段代码是无法判断执行速度的。

大多数编译器都会优化您的代码，因此除非您喜欢研究操作码，否则要告诉哪个会更快预编译并不容易。

在速度方面，您应该对代码进行基准测试。强调它，看看它的表现如何。

但效率不仅仅与速度有关。您还应该考虑哪一种适合您的编码风格。就个人而言，我讨厌看到随机的块，你甚至可以在研究它们被复制粘贴的代码之前就知道它们。

+把它贴在那里：codereview

于 2013-08-01T14:17:31.023 回答