5

在这个问题中，我们只考虑由小写英文字母 (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) 是palindromic 因为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");}
4

3 回答 3

1

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

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

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

例如。

关于时间复杂度 - 正如您可以在此处阅读的那样，您无法在 o(n) 中检查它们。

于 2013-07-28T14:54:16.443 回答
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;
}
于 2013-07-28T14:52:43.717 回答
0

我会简单地删除递归（算法稍作改动）：

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;
}
于 2013-07-28T23:33:38.573 回答