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)