Java程序查找字符串的所有回文子串

---

在这个问题中，我们得到一个字符串，我们的任务是找到指定长度的所有回文子串。有两种方法可以解决这个问题。第一种方法是比较子串从头到尾的字符，另一种方法是反转子串并将其与原始子串进行比较，以检查它是否是回文。

字符串在Java中是一个类，它表示一系列字符。它是不可变的，这意味着一旦创建了String对象，就不能更改它。并且，子串是字符串的一小部分或一部分。

示例场景1

Input: string str = "abcd"
Output: res = 4

回文子串是'a'、'b'、'c'和'd'。

示例场景2

Input: string str = "abbab"
Output: res = 8

回文子串是'a'、'abba'、'b'、'bb'、'b'、'bab'、'a'、'b'。

使用for循环

在这种方法中，我们将使用for循环来获取给定字符串的所有子串。我们将匹配从开始和结束的子串的字符，以检查该字符串是否为回文。如果任何字符不匹配，我们可以说该字符串不是回文，然后继续。

示例

下面的Java程序演示了如何使用for循环查找给定字符串的回文子串。

import java.io.*;

public class Main {
   public static boolean isPalindrome(String temp) {
      int len = temp.length();
      // Match string characters from the start and end
      for (int m = 0; m < len / 2; m++) {
         if (temp.charAt(m) != temp.charAt(len - m - 1)) {
            return false;
         }
      }
      return true;
   }
   public static void main(String[] args) {
      // Custom input string
      String alpha = "abcd";
      // To store the total number of palindromic substrings
      int palCounts = 0;
      // Get all substrings starting with index p.
      for (int p = 0; p < alpha.length(); p++) {
         // Get all substrings ending at q index
         for (int q = p; q < alpha.length(); q++) {
            // Get Substring
            String subStr = alpha.substring(p, q + 1);
            // If the string is a palindrome, increment count
            if (isPalindrome(subStr)) {
               palCounts++;
            }
         }
      }
      System.out.println("The total number of palindromic substrings of the given string is " + palCounts);
   }
}

运行此代码后，它将生成以下结果：

The total number of palindromic substrings of the given string is 4

以下是时间和空间复杂度：

//To find all substrings and checking whether it is palindromic.
Time complexity − O(N^3)
//To store the substring
Space complexity − O(N)

使用while循环

在这种方法中，我们将使用while循环来获取给定字符串的所有子串。之后，我们将使用reverse()方法反转字符串，并将其与原始子串进行比较，以检查它是否是回文。

示例

在这个Java程序中，我们使用while循环来打印查找给定字符串的回文子串。

import java.io.*;

public class Main {
   public static void main(String[] args) {
      // Custom input string
      String alpha = "abcd";
      // To store the total number of palindromic substrings
      int palCounts = 0;
      int p = 0;
      // Get all substrings starting with index p.
      while (p < alpha.length()) {
         int q = p;
         // Get all substrings ending at q index
         while (q < alpha.length()) {
            // Get Substring
            String subStr = alpha.substring(p, q + 1);
            // Reverse substring
            String rev = new StringBuffer(subStr).reverse().toString();
            // If substring and its reverse are equal
            if (subStr.equals(rev)) {
               palCounts++;
            }
            q++;
         }
         p++;
      }
      System.out.println("The total number of palindromic substrings of the given string is " + palCounts);
   }
}

上述代码的输出如下：

The total number of palindromic substrings of the given string is 4

以下是时间和空间复杂度：

//To get all substrings and reverse each substring
Time complexity − O(N^3)
//To store the reversed substring
Space complexity − O(N)