相关疑难解决方法(0)

例如字符串"abaccddccefe"中的"ccddcc"

我想到了一个解决方案,但它在O(n ^ 2)时间运行

Algo 1:

步骤:它是一种强力方法

1. 对于j = i + 1到j小于array.length,
   对于i = 1到i小于array.length -1
   , 有2个for循环
2. 这样,您可以从数组中获取每个可能组合的子字符串
3. 有一个回文功能,检查字符串是否是回文
4. 所以对于每个子串(i,j)调用这个函数,如果它是一个回文存储它在一个字符串变量中
5. 如果您找到下一个回文子串并且如果它大于当前回归,则将其替换为当前的回归.
6. 最后你的字符串变量将有答案

问题:1.这个算法在O(n ^ 2)时间运行.

算法2:

1. 反转字符串并将其存储在不同的数组中
2. 现在找到两个数组之间最大的匹配子字符串
3. 但这也是在O(n ^ 2)时间内运行的

你们能想到一个在更好的时间里运行的算法吗？如果可能的话O(n)时间

在这个问题中,我们只考虑由小写英文字母(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 …