JAVA算法:回文字符串相关问题详解(回文字符串总结)

JAVA算法:回文字符串相关问题详解(回文字符串总结)JAVA算法:回文字符串相关问题详解(回文字符串总结)Q1.编写一个工具方法判断给定的字符串是否为回文字符串例如:给定一个字符串“aabbaa”,判断该字符串是否为回文字符串。算法设计如下: /* *给定一个字符串,判断该字符串是否为一个回文字符串 *start表示需要判断的起始位置 *end表示需要判断的结束位置 */ publicstatic…

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

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账号...

(0)


相关推荐

  • plc上位机软件编程_有上位机还必须用plc吗

    plc上位机软件编程_有上位机还必须用plc吗1、PLC的发展历程在工业生产过程中,大量的开关量顺序控制,它按照逻辑条件进行顺序动作,并按照逻辑关系进行连锁保护动作的控制,及大量离散量的数据采集。传统上,这些功能是通过气动或电气控制系统来实现的。1968年美国GM(通用汽车)公司提出取代继电气控制装置的要求,第二年,美国数字公司研制出了基于集成电路和电子技术的控制装置,首次采用程序化的手段应用于电气控制,这就是代可编程序控制器,称Progra…

  • Django(22)Django执行SQL语句

    Django(22)Django执行SQL语句前言Django在查询数据时,大多数查询都能使用ORM提供的API方法,但对于一些复杂的查询可能难以使用ORM的API方法实现,因此Django引入了SQL语句的执行方法,有以下三种执行方式ext

  • Pytest(6)重复运行用例pytest-repeat[通俗易懂]

    Pytest(6)重复运行用例pytest-repeat[通俗易懂]前言平常在做功能测试的时候,经常会遇到某个模块不稳定,偶然会出现一些bug,对于这种问题我们会针对此用例反复执行多次,最终复现出问题来。自动化运行用例时候,也会出现偶然的bug,可以针对单个用例,

  • java的反射机制带来的好处_java注解原理

    java的反射机制带来的好处_java注解原理什么是反射Java的反射(reflection)机制是指在程序的运行状态中,可以构造任意一个类的对象,可以了解任意一个对象所属的类,可以了解任意一个类的成员变量和方法,可以调用任意一个对象的属性和方法jdbc(数据库连接技术)在加载驱动时运用到了反射技术例如:实例化对象第一种:Personp=newPerson()虚拟机在执行的时候已经确切知道要实例化哪个类的对象第二种:反射:虚拟机在实例化对象的时候,可以事先不知道要实例化哪个类的对象,传参的时候虚拟机根据参数确定要实例化哪个类的

  • getComputedStyle()与currentStyle()、style()方法「建议收藏」

    JS使用getComputedStyle()方法获取CSS属性值 在对网页进行调试的过程中,经常会用到js来获取元素的CSS样式,方法有很多很多,现在仅把我经常用的方法总结如下:1.obj.style:这个方法只能JS只能获取写在html标签中的写在style属性中的值(style=”…”),而无法获取定义在&lt;styletype="text/c…

  • powerdesigner创建数据库模型(概念模型举例)

    1.启动PowerDesigner(我用的PowerDesigner16.7破解版)选择新建概念模型进行数据库设计的E-R模型辅助设计2.概念模型的设计实体:选择实体图形,在“图纸”点击划出实体来,双击为其命名,选择Attributes添加其所有属性。注意所有的name都可以用中文标示,以好理解;但是code必须用英文标示,以方便库的操作处理(PowerDesigner转化数据库.sql文件,所有的表名称,属性等都采用code)。为每个属性命名,并选择相应的数据类型,PowerDesigner

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号