java - 计算一个字符串中有多少个回文

Question

我想使用给定字符串的子字符串找出所有可能的回文。

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

这里时间复杂度比较高，如何提高这个逻辑的性能？

Answer 1

以下是您在优化此算法时可以考虑的一些事项:

1. 什么是回文？回文是一个对称字符串，这意味着它必须有一个中心轴!枢轴可以是以下之一:

   • 一个字母，如“aba”，或者

   • 两个字母之间的位置，如字母“aa”之间的位置

这意味着总共有 2n − 1 个可能的支点。

然后，您可以从每个枢轴向外搜索。这是一个例子:

• 示例字符串:“abcba”
• 首先，让我们以“c”为轴:
  • abcba → c 是回文，然后在每边将搜索范围扩大 1。
  • abcba → bcb 是回文，然后在每边将搜索范围扩大 1。
  • abcba → abcba 是回文，所以我们知道字符串中至少有 3 个回文。
• 对所有枢轴继续此操作。

采用这种方法，运行时复杂度为 O(n²)。