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

javaobject oriented programmingprogramming更新于 2024/7/30 19:24:17

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

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

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

示例

输入

alpha = "abcd"

输出

4

解释

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

输入

alpha = "pqp"

输出

4

解释

回文子串为'p'、'q'、'p'和'pqp'。

输入

alpha = "abbab"

输出

8

解释

回文子字符串为 'a'、'abba'、'b'、'bb'、'b'、'bab'、'a'、'b'。

方法 1

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

算法

  • 步骤 1 - 用 0 初始化"palCounts"以存储给定字符串的回文字符串数量

  • 步骤 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();
      // 从开始和结束匹配字符串字符
      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) {
      // 自定义输入字符串
      String alpha = "abcd";
      // 存储回文子串的总数
      int palCounts = 0;
      // 获取以索引 p 开头的所有子字符串。
      for (int p = 0; p < alpha.length(); p++) {
         // 获取以 q 索引结尾的所有子字符串
         for (int q = p; q < alpha.length(); q++) {
            // 获取子字符串
            String subStr = alpha.substring(p, q + 1);
            // 如果字符串是回文,则增加计数
            if (isPalindrome(subStr)) {
               palCounts++;
            }
         }
      }
      System.out.println("给定字符串的纯文本子字符串总数为 " + palCounts);
   }
}

输出

给定字符串的纯文本子字符串总数为 4

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

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

方法 2

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

算法

  • 步骤 1 - 用 0 初始化"palCounts"以存储回文子字符串的数量。

  • 步骤 2 - 用 0 初始化"p",并遍历字符串,直到"p"小于长度。

  • 步骤 3 - 用"p"初始化"q",并遍历字符串,直到"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) {
    // 自定义输入字符串
    String alpha = "abcd";
    // 存储回文子字符串的总数
    int palCounts = 0;
    int p = 0;
    // 获取以索引 p 开头的所有子字符串。
    while (p < alpha.length()) {
         int q = p;
         // Get all substrings ending at q index
         while (q < alpha.length()) {
            // 获取子字符串
            String subStr = alpha.substring(p, q + 1);
            // 反向子字符串
            String rev = new StringBuffer(subStr).reverse().toString();
            // 如果子字符串与其反向相等
            if (subStr.equals(rev)) {
            	palCounts++;
            }
            q++;
         }
         p++;
      }
      System.out.println("给定字符串的纯文本子字符串总数为 " + palCounts);
	}
}

输出

给定字符串的纯文本子字符串总数为 4

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

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

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


相关文章


有用资源