需要算法帮助(Codility)

Question

在这个问题中,我们只考虑由小写英文字母(a-z)组成的字符串.如果从左到右读取与从右到左完全相同的字符串,则字符串是回文.

例如,这些字符串是回文:

aza
abba
abacaba

这些字符串不是回文:

zaza
abcd
abacada

给定长度为N的字符串S,S的切片是由一对整数(p,q)指定的S的子串,使得0 ? p < q < N.如果由字母组成的字符串是回文,则字符串S的切片(p,q)S[p], S[p+1], ..., S[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");}

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;
}