Java 查找给定字符串的所有回文子串

在这个问题中，我们将找到给定长度的所有回文子串。

解决这个问题有两种方法。第一种方法是从开头到结尾比较子字符串的字符，另一种方法是反转子字符串并将其与原始子字符串进行比较以检查子字符串是否是回文。

问题描述 −我们给定了一个字符串alpha。我们需要找到给定字符串的所有回文子串。

示例

输入

alpha = "abcd"

输出

4

解释

The palindromic substrings are ‘a’, ‘b’, ‘c’, and ‘d’.

输入

alpha = "pqp"

输出

4

解释

The palindromic substrings are ‘p’, ‘q’, ‘p’, and ‘pqp’.

输入

alpha = "abbab"

输出

8

解释

The palindromic substrings are ‘a’, ‘abba’, ‘b’, ‘bb’, ‘b’, ‘bab’, ‘a’, ‘b’.

方法1

在这个方法中，我们将使用 for 循环来获取给定字符串的所有子字符串。我们将从开头和结尾匹配子字符串的字符，以检查字符串是否是回文。如果任何字符不匹配，我们可以说字符串不是回文并继续向前。

步骤

• 步骤 1 - 将 ‘palCounts’ 初始化为 0，以存储给定字符串的回文字符串的数量。

• 步骤 2 - 使用两个嵌套的 for 循环来获取给定字符串的所有子字符串。

• 步骤 3 - 使用 substring() 方法从 p 索引到 q + 1 索引获取子字符串。

• 步骤 4 - 执行 isPalindrome() 函数来检查子字符串是否是回文的。

• 步骤 4.1 - 在 isPalindromic() 函数中，使用循环遍历字符串直到 ‘len/2’ 索引。

• 步骤 4.2 - 如果 ‘m’ 索引和 ‘len – m – 1’ 索引处的字符不相同，则返回 false。

• 步骤 4.3 - 最后返回 true。

• 步骤 5 - 如果字符串是回文的，则将 ‘palCounts’ 增加 1。

• 步骤 6 - 返回 ‘palCounts’。

示例

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 plaindromic substrings of the given string is " + palCounts);
   }
}

输出

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

时间复杂度 – O(N^3)，用于找到所有子字符串并检查是否是回文。

空间复杂度 – O(N)，用于存储子字符串。

方法2

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

步骤

• 步骤1 - 将’palCounts’初始化为0，用于存储回文子字符串的计数。

• 步骤2 - 将’p’初始化为0，并遍历字符串直到’p’小于长度。

• 步骤3 - 将’q’初始化为’p’，并遍历字符串直到’q’小于字符串长度。

• 步骤4 - 使用substring()方法从p到q + 1索引获取子字符串。

• 步骤5 - 使用StringBuffer()创建一个字符串缓冲区，并使用reverse()方法反转字符串。同时，我们还需要使用toString()方法从字符串缓冲区创建字符串。

• 步骤6 - 使用equals()方法检查反转字符串是否与原始字符串相同。

• 步骤7 - 如果是，则增加’palCounts’的计数。

• 步骤8 - 返回’palCounts’的值。

示例

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 plaindromic substrings of the given string is " + palCounts);
   }
}

输出

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

时间复杂度-获取所有子字符串并反转每个子字符串的时间复杂度为O(N^3)。

空间复杂度-存储反转后的子字符串的空间复杂度为O(N)。

两种方法的时间复杂度相同，但使用不同的逻辑来检查回文字符串。第一种方法比第二种方法更快，因为它直接比较字符串字符而无需反转字符串。