この問題では、小文字の英字 (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、回文です。
長さ N 文字の文字列 S を指定して、S の回文スライスの数を返す関数を作成しますint solution(const string &S);。この数が 100,000,000 より大きい場合、関数は -1 を返す必要があります。
たとえば、stringS = baababaの場合、そのスライスの正確に 6 つが回文であるため、関数は 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");}