JAVA算法：回文字符串相关问题详解（回文字符串总结）

您所在的位置：网站首页 › 所有标点符号的含义 › JAVA算法：回文字符串相关问题详解（回文字符串总结）

JAVA算法：回文字符串相关问题详解（回文字符串总结）

2024-07-13 11:54| 来源: 网络整理| 查看: 265

大家好，又见面了，我是你们的朋友全栈君。

JAVA算法：回文字符串相关问题详解（回文字符串总结）Q1. 编写一个工具方法判断给定的字符串是否为回文字符串

例如：给定一个字符串“aabbaa”，判断该字符串是否为回文字符串。

算法设计如下：

代码语言：javascript复制 /* * 给定一个字符串，判断该字符串是否为一个回文字符串 * start表示需要判断的起始位置 * end表示需要判断的结束位置 */ public static boolean isPalindrome(String input, int start, int end) { while (start < end) { if (input.charAt(start++) != input.charAt(end--)) return false; } return true; }

完整的测试代码如下：

代码语言：javascript复制package com.bean.algorithm.palindromic; public class PalindromicUtils { /* * 给定一个字符串，判断该字符串是否为一个回文字符串 * start表示需要判断的起始位置 * end表示需要判断的结束位置 */ public static boolean isPalindrome(String input, int start, int end) { while (start < end) { if (input.charAt(start++) != input.charAt(end--)) return false; } return true; } public static void main(String[] args) { // TODO Auto-generated method stub String str="aabbaa "; //String str="fafadabcbafdfdfas"; //注意去掉字符串前后的空格 str=str.trim(); boolean flag=isPalindrome(str,0,str.length()-1); System.out.println("Flag is: "+flag); } }

程序运行结果;

Flag is: true

Q2. 求给定字符串中的最长回文子串

输入一个字符串，求出其中最长的回文子串。

子串的含义是：在原串中连续出现的字符串片段。

在求解这个问题的时候，一定要看清楚问题。不要混淆“子串”和“子序列”的概念。“子串”是指在源字符串中连续出现的字符串片段；而“子序列”是指在源字符串中可以不连续出现的字符串片段。一个连续，一个不连续。

回文的含义是：子串从左向右看和从右向左看是相同的，例如：abba，yyxyy。在判断时忽略所有标点符号和空格，且忽略大小写，但是输出应保持原样。输入字符串的长度不超过5000，且占据单独一行。应该输出最长的回文串。如果有多个，输出起始位置最靠左的一个。

例如给定字符串：fafadabcbafdfdfas

其最长回文子串为：afdfdfa

算法设计如下：

代码语言：javascript复制package com.bean.algorithmexec; import java.io.FileNotFoundException; public class LongestPalindromeString3 { /* * * 输入一个字符串，求出其中最长的回文子串。 * 子串的含义是：在原串中连续出现的字符串片段。 * 回文的含义是：子串从左向右看和从右向左看是相同的，例如：abba，yyxyy。在判断时忽略所有标点符号和空格，且忽略大小写，但是输出应保持原样。 * 输入字符串的长度不超过5000，且占据单独一行。应该输出最长的回文串。如果有多个，输出起始位置最靠左的一个。 * */ /* * 动态规划算法 * dp(i, j) 表示是否 s(i ... j) 能够形成一个回文字符串 * 当 s(i) 等于 s(j) 并且 s(i+1 ... j-1) 是一个回文字符串时 dp(i, j) 的取值为 true * 当我们找到一个回文子字符串时，我们检查其是否为最长的回文字符串 */ public static String longestPalindrome(String s) { // n表示字符串的长度 int n = s.length(); String res = null; // 定义一个dp数组 boolean[][] dp = new boolean[n][n]; // 外层循环控制从最后一个字符向第一个字符渐进 for (int i = n - 1; i >= 0; i--) { // 内层循环控制 for (int j = i; j < n; j++) { // dp数组元素 dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]); if (dp[i][j] && (res == null || j - i + 1 > res.length())) { res = s.substring(i, j + 1); } } } return res; } public static void main(String[] args) throws FileNotFoundException { // 读取输入的字符串 String strdemo = "fafadabcbafdfdfas"; String ANSWER = longestPalindrome(strdemo); System.out.println(ANSWER); } }

程序运行结果：

afdfdfa

另外一种算法：

代码语言：javascript复制package com.bean.algorithmexec; public class LongestPalindromeString4 { static void printSubStr(String str, int low, int high) { System.out.println(str.substring(low, high + 1)); } static int longestPalSubstr(String str) { int maxLength = 1; int start = 0; int len = str.length(); int low, high; for (int i = 1; i < len; ++i) { low = i - 1; high = i; while (low >= 0 && high < len && str.charAt(low) == str.charAt(high)) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } --low; ++high; } low = i - 1; high = i + 1; while (low >= 0 && high < len && str.charAt(low) == str.charAt(high)) { if (high - low + 1 > maxLength) { start = low; maxLength = high - low + 1; } --low; ++high; } } System.out.print("最长回文子串为: "); printSubStr(str, start, start + maxLength - 1); return maxLength; } public static void main(String[] args) { String str = "fafadabcbafdfdfas"; System.out.println("长度是: " + longestPalSubstr(str)); } }

程序运行结果为：

最长回文子串为: afdfdfa 长度是: 7

Q3. 对于给定的字符串输出所有可能的回文子串分区

例如：给定字符串 str = “bcc”

输出结果为：[“b”, “c”, “c”], [“b”, “cc”]

算法设计：

代码语言：javascript复制package com.bean.algorithm.palindromic; import java.util.ArrayList; import java.util.Deque; import java.util.LinkedList; public class PrintAllPalindrome { public static void main(String[] args) { String input = "abbcbba"; //String input = "fafadabcbafdfdfas "; System.out.println("对于给定的字符串 " + input + " 的所有可能的回文分区 :"); allPalPartitions(input); } private static void allPalPartitions(String input) { int n = input.length(); // 用于存放所有回文子串（ palindromic partitions） ArrayList allPart = new ArrayList(); // 用于存放当前回文子串（ palindromic partitions） Deque currPart = new LinkedList(); // 递归调用方法生成所有分区部分 allPalPartitonsUtil(allPart, currPart, 0, n, input); // 输出所有分区部分字符串 for (int i = 0; i < allPart.size(); i++) { for (int j = 0; j < allPart.get(i).size(); j++) { System.out.print(allPart.get(i).get(j) + " "); } System.out.println(); } } private static void allPalPartitonsUtil(ArrayList allPart, Deque currPart, int start, int n, String input) { if (start >= n) { allPart.add(new ArrayList(currPart)); return; } for (int i = start; i < n; i++) { // 如果子串 str[start..i] 是回文子串（ palindrome） if (isPalindrome(input, start, i)) { currPart.addLast(input.substring(start, i + 1)); allPalPartitonsUtil(allPart, currPart, i + 1, n, input); // 从当前分区中删除子串 str[start..i] currPart.removeLast(); } } } // 判断字符串是否为回文字符串（Palindrome）的工具方法（utility function） private static boolean isPalindrome(String input, int start, int i) { while (start < i) { if (input.charAt(start++) != input.charAt(i--)) return false; } return true; } }

程序运行结果：

对于给定的字符串 abbcbba 的所有可能的回文分区 : a b b c b b a a b b c bb a a b bcb b a a bb c b b a a bb c bb a a bbcbb a abbcbba

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/141891.html原文链接：https://javaforall.cn

【本文地址】

JAVA算法：回文字符串相关问题详解（回文字符串总结）

JAVA算法：回文字符串相关问题详解（回文字符串总结）

今日新闻

推荐新闻