大家好,又见面了,我是你们的朋友全栈君。
JAVA算法:回文字符串相关问题详解(回文字符串总结)
Q1. 编写一个工具方法判断给定的字符串是否为回文字符串
例如:给定一个字符串“aabbaa”,判断该字符串是否为回文字符串。
算法设计如下:
/*
* 给定一个字符串,判断该字符串是否为一个回文字符串
* 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;
}
完整的测试代码如下:
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
算法设计如下:
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
另外一种算法:
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”]
算法设计:
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<ArrayList<String>> allPart = new ArrayList<>();
// 用于存放当前回文子串( palindromic partitions)
Deque<String> currPart = new LinkedList<String>();
// 递归调用方法生成所有分区部分
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<ArrayList<String>> allPart, Deque<String> 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
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/141891.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...