我想使用给定字符串的子字符串找出所有可能的回文。
Example: input = abbcbbd.
Possible palindromes are a,b,b,c,b,b,d,bb,bcb, bbcbb,bb
这是我实现的逻辑:
public int palindromeCount(String input) {
int size = input.length();// all single characters in string are treated as palindromes.
int count = size;
for(int i=0; i<size; i++) {
for(int j=i+2; j<=size; j++) {
String value = input.substring(i, j);
String reverse = new StringBuilder(value).reverse().toString();
if(value.equals(reverse)) {
count++;
}
}
}
return count;
}
这里时间复杂度比较高,如何提高这个逻辑的性能?
最佳答案
以下是您在优化此算法时可以考虑的一些事项:
什么是回文?回文是一个对称字符串,这意味着它必须有一个中心轴!枢轴可以是以下之一:
一个字母,如“aba”,或者
两个字母之间的位置,如字母“aa”之间的位置
这意味着总共有 2n − 1 个可能的支点。
然后,您可以从每个枢轴向外搜索。这是一个例子:
- 示例字符串:“abcba”
- 首先,让我们以“c”为轴:
- abcba → c 是回文,然后在每边将搜索范围扩大 1。
- abcba → bcb 是回文,然后在每边将搜索范围扩大 1。
- abcba → abcba 是回文,所以我们知道字符串中至少有 3 个回文。
- 对所有枢轴继续此操作。
采用这种方法,运行时复杂度为 O(n2)。
关于java - 计算一个字符串中有多少个回文,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56677100/