需要算法帮助（Codility）

Question

在这个问题中，我们只考虑由小写英文字母（a-z）组成的字符串。 如果一个字符串从左到右读起来和从右到左读起来完全一样，那么它就是回文字符串。

例如，以下字符串是回文字符串：

aza
abba
abacaba

这些字符串不是回文：

zaza
abcd
abacada

给定长度为N的字符串S，字符串S的一个切片是由一对整数(p, q)指定的S子串，其中0 ≤ p < q < N。如果由字母S[p], S[p+1], ..., S[q]组成的字符串是回文的，则字符串S的切片(p, q)是回文的。

例如，在字符串S = abbacada中：

切片(0, 3)是回文的，因为abba是回文的，
切片(6, 7)不是回文的，因为da不是回文的，
切片(2, 5)不是回文的，因为baca不是回文的，
切片(1, 2)是回文的，因为bb是回文的。

---

编写函数int solution(const string &S)，给定长度为N的字符串S，返回字符串S的回文切片数。如果此数字大于100,000,000，则函数应返回-1。

例如，对于字符串S = baababa，函数应该返回6，因为它的六个切片都是回文的：即(0, 3), (1, 2), (2, 4), (2, 6), (3, 5), (4, 6)。

假设：
- N是在范围[0..20,000]内的整数；
- 字符串S仅由小写字母(a-z)组成。

复杂度：
- 预期的最坏时间复杂度为O(N);
- 预期的最坏空间复杂度为O(N)（不包括所需的输入参数存储）。

以下是我的解决方案：

int palindrom(const string &S, int startIndex,int endIndex, int counter=0)
{ 
    bool equals = true;
    if (endIndex - startIndex < 1)
        return counter;
    for(int i = startIndex,j = endIndex;i<j; ++i, --j)
    {
        equals = S[i] == S[j];
        if (!equals) break;
    }
    if (equals) counter++;
    counter = palindrom( S,startIndex,endIndex-1,counter);
    return counter;
}

int solution(const string &S)
{
    int length = S.size();
    int counter = 0;
    if (length > 20000) return -1;
    for(int i=0; i < length-1; i++)
    {
        counter += palindrom(S,i,length-1);
        if (counter > 100000000) return -1;
    }
    return counter;
}

对于字符串长度 S.size() > 3000，我总是会遇到运行时错误（意味着时间超过了 3 秒，但解决方案应该在少于 2 秒的时间内工作）！有什么建议吗？

好的！主函数大致如下：

main(){cout<<solution("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa");}

- devworkstation

---

请格式化你的代码，以便我们不需要滚动就能阅读它。同时，请提供错误信息，以便我们可以做出知情的猜测。请告诉我你正在运行哪个平台？你正在使用哪个编译器？ - EvilTeach

不要错过格式帮助，在这样的问题上非常需要。如果你让别人更容易做事，他们会更愿意为你工作。 - Cody Gray

踩负评是没有意义的。给他改进问题的机会。这看起来是一个有趣的问题。 - EvilTeach

@devworkstation 你必须使用[编辑]链接，不能提交与此完全相同的新问题。否则我不确定你遇到了什么问题。Jrok已经格式化了大的代码块，但你应该能够添加换行符来创建段落，并用反引号（``）包围内联代码块。 - Cody Gray

你能发布 main() 和你的输入文本吗？ - cdmh

Answer 1

我会避免使用递归。

#include <string>
#include <iostream>

typedef std::string::const_iterator P;

bool is_palindrom(P begin, P end) {
    while (begin < end) {
        if (*begin != *end)
            return false;
        ++begin;
        --end;
    }
    return true;
}

int count_palindroms(const std::string &s) {
    int c = 0;
    P left = s.begin();
    while (left < s.end()) {
        P right = left + 1; // because length palindrome > 1
        while (right < s.end()) {
            if (is_palindrom(left, right)) {
                //std::cout << left - s.begin() << ' ' << right - s.begin() << std::endl;
                c++;
                if (c > 100000000)
                    return -1;
            }
            ++right;
        }
        ++left;
    }
    return c;
}

int main(int , char *[])
{
    std::cout << count_palindroms("baababa") << std::endl;
    return 0;
}

- CapelliC

---

谢谢回复！对我来说，我的解决方案看起来更易读。但无论如何，你的解决方案仍然非常慢。 - devworkstation

Answer 2

这在我的电脑上运行良好。 你实际上在检查原始字符串的每个子字符串并对其运行递归函数。 正如@PeterT所提到的，你可能达到了你卡住的最大深度。

我会做的是不使用调用堆栈，而是使用自己的卡住，或者使用一些简单的字符串函数，例如：

std::string s = "aba";
std::string s1 = std::string(s.rbegin(), s.rend()); 
if (s == s1)
{
///...
}

举个例子。

关于时间复杂度 - 正如您可以在这里阅读的那样，您无法在O(n)中检查所有内容。

- asafrob

---

他不想打印所有字符串，只想计算它们的数量。这可能会使“O(n^2)”的证明无效。尽管可以承认，我也认为这不能在“O(n)”内完成。 - tohava

Answer 3

我会简单地删除递归（并对算法进行小改动）：

int palindrom(const string &S, int startIndex, int endIndex, int counter = 0)
{
    for (int k = endIndex; k > startIndex; --k) {
        bool equals = true;
        for (int i = startIndex, j = k; i < j; ++i, --j)
            if (S[i] != S[j]) {
                equals = false;
                break;
            }
        if (equals)
            counter++;
    }
    return counter;
}

- Kyle_the_hacker