查找字符串中的最长回文串（JAVA实现）_java获取字符串最长回文串

思路写在代码里

判断一个字符串是否是回文串

    /***********************
	 * 判断一个字符串是否是回文串（左右对称）  单个数字默认为是
	 * @param str 需要进行判断的字符串
	 * @return 返回该整数是否为回文串
	 */
    public static boolean isPlalindrome(String str) {
    	//将字符串转化为字符数组
        char[] array=str.toCharArray();
        int left=0,right=array.length-1;//记录数组的开始位置和结束位置
        while(left<right)//开始位置小于结束位置时，进行判断  两位置处于对称位置上
        {
            if(array[left++]!=array[right--])//如果两位值的字符不相同 则不对称
                return false;//返回false
        }
        //所有位除奇数位时的中间位均对应 返回true
        return true;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

暴力法查找字符串中的最长回文串

/**************************
 * 求解字符串的最长回文串----暴力法 O(n^3)
 * 通过两层循环找出字符串的所有子串  对每一个子串进行判断 
 * 将是回文串的子串储存  当有新的回文串时，比较记录中的回文串和当前回文串的长度
 * 用较长的串替换当前串  如果两串长度相同，保留旧的
 * PS：如果想保存所有的回文串 可以修改记录回文串的结构为String数组（链表、hash表都可以）
 * @param str 要求解的字符串
 * @return 返回字符串中的最长回文串
 */
public static String longestPlalindrome(String original)
{
	//非空判断
	if((original==null)||original.length()==0)
	{
		return null;
	}
	//将字符串转换为字符数组
	char[] oriArray=original.toCharArray();
	int first=0;
	int end=0;//当前字符串中回文串的始末位置 包含末位置
	
	for(int i=0;i<oriArray.length-1;i++)//两次循环 查找字符串的所有子串
	{
		for(int j=i;j<oriArray.length;j++)
		{
			//判断子串是否为回文串
			int left=i,right=j;//记录左侧右侧的位置
			while(left<right)//左侧下标小于右侧下标时 比较未完成
			{
				if(oriArray[left]!=oriArray[right])
					break;//如果出现对称位置不相等元素  则不是回文串跳出循环
			//判断下一对称位置
				left++;
				right--;
				
			}
			if(left>=right)//是否比较完成 是字符串是否为回文串的判断条件
			{
				if(j-i>end-first)//查找到回文串 且长度大于当前存储的回文串长度
				{
					//替换当前回文串
					first=i;
					end=j;
				}
			}
			/*if(isPlalindrome(oriArray,i,j))//是回文串
			{
				if(j-i>end-first)//查找到回文串 
				{
					//替换当前回文串
					first=i;
					end=j;
				}
			}*/
		}
	}
	//查找结束  将数组转化为字符串返回
	return String.valueOf(oriArray, first, end+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

中心拓展法查找字符串中的最长回文串

/*****************************
 * 求解字符串中的最长回文串 -----中心拓展法O(n^2)
 * 基本思路  选择一个字符作为中心 向两边查找回文串
 * 但是查找过程中需要将长度为奇数的回文串和长度为偶数的回文串分开考虑
 * @param str 要求解的字符串
 * @return 返回字符串中的最长回文串
 */
public static String longestPlalindromeCenter(String original)
{
	//非空判断
	if((original==null)||original.length()==0)
	{
		return null;
	}
	//将字符串转换为字符数组
	char[] oriArray=original.toCharArray();
	int first=0;
	int end=0;//当前字符串中回文串的始末位置 包括末位置
	
	//查找奇数位的回文串
	for(int i=0;i<oriArray.length;i++)
	{
		//i为中心点  从i开始向两边进行判断
		int preI=i-1,sufI=i+1;//中心点之前和之后的元素
		while((preI>=0)&&(sufI<oriArray.length)&&(oriArray[preI]==oriArray[sufI]))
		{
			//两侧元素相等时 继续向两边进行判断
			preI--;
			sufI++;
		}
		//当前回文串的长度大于存储中的回文串的长度
		//为什么是减2呢？因为最后preI和sufI下标所在位置的值是不相同的 相同的是preI+1和sufI-1位置的值
		if(sufI-preI-2>end-first)
		{
			first=preI+1;
			end=sufI-1;
		}
	}
	//查找偶数位的回文串
	for(int i=0;i<oriArray.length-1;i++)//只需要到倒数第二位  因为偶数位的判断，需要判断随后一位是否与当前位相同
	{
		//相邻位置不相同
		if(oriArray[i+1]!=oriArray[i])
		{
			continue;
		}
		else
		{
			//i和i+1为中心点  从i开始向两边进行判断 
			int preI=i-1,sufI=i+2;
			while((preI>=0)&&(sufI<oriArray.length)&&(oriArray[preI]==oriArray[sufI]))
			{
				//两侧元素相等时 继续向两边进行判断
				preI--;
				sufI++;
			}
			//当前回文串的长度大于存储中的回文串的长度
			if(sufI-preI-2>end-first)
			{
				first=preI+1;
				end=sufI-1;
			}
		}
	}
	//查找结束  将数组转化为字符串返回
	return String.valueOf(oriArray, first, end-first+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

动态规划法查找字符串中的最长回文串

/*************************
 * 求解字符串中的最长回文串-----动态规划法O(n^2)
 * 实现思路:用一个boolean类型的二维数组isPlalindrome[i][j] 来表示i到j之间的字符串是否回文
 * 其中 i>=j
 * 动态规划的初值就是  当i=j时，isPlalindrome[i][j]=true;
 * 动态规划的推导公式为  当i=j+1时，isPlalindrome[i][j]=(oriArray[i]==oriArray[j]),相邻两元素是否相等
 * 					当i>j+1时，需要判断i与j之间的子串是否是回文串,即
 * 							isPlalindrome[i][j]=(oriArray[i]==oriArray[j])&&isPlalindrome[i+1][j-1]
 * PS:状态矩阵赋值过程必须使用左下三角的形式  否则会产生误判 使用了未赋值的位置
 * @param str 要求解的字符串
 * @return 返回字符串中的最长回文串
 */
public static String longestPlalindromeDynamic(String original)
{
	//非空判断
	if((original==null)||original.length()==0)
	{
		return null;
	}
	//将字符串转换为字符数组
	char[] oriArray=original.toCharArray();
	int first=0;
	int end=0;//当前字符串中回文串的始末位置 包括末位置
	
	boolean[][] isPlalindrome=new boolean[oriArray.length][oriArray.length];
	//动归过程
	for(int i=0;i<oriArray.length;i++)
	{
		for(int j=0;j<=i;j++)
		{
			/*if(i==j)//同一位置
			{
				isPlalindrome[i][j]=true;
			}
			else if(j-i==1)//相邻元素
			{
				isPlalindrome[i][j]=(oriArray[i]==oriArray[j]);
			}*///合并为以下部分 这两部分都是可直接求解的
			if(i-j<2)
			{
				isPlalindrome[i][j]=(oriArray[i]==oriArray[j]);
			}
			else//不相邻的元素
			{
				isPlalindrome[i][j]=((oriArray[i]==oriArray[j])&&isPlalindrome[i-1][j+1]);
			}
			//一次动归过程完成 判断当前是否为回文串 如果是 长度是否大于当前存储的回文串
			if(isPlalindrome[i][j]&&(i-j)>end-first)
			{
				first=j;
				end=i;
			}
		}
	}
	//查找结束  将数组转化为字符串返回
	return String.valueOf(oriArray, first, end+1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

马拉车法查找字符串中的最长回文串（Manacher’s Algorithm）

/****************************
 * 求解字符串中的最长回文串----马拉车方法(Manacher's Algorithm)  O(n)
 * 实现思路:和中心拓展法比较相似
 * 首先预处理原字符串
 * 在最开始添加特殊符号
 * 然后在字符串的每个字符之间以及开始和末尾添加另一种特殊符号，解决奇数回文串和偶数回文串的问题
 * 创建与处理后数组等长的辅助数组   assistArray[i]表示以changeArray[i]为中心的最长回文子串的半径，
 * 求解辅助数组引入mx和id两个变量 mx是回文串能延伸到的最右端的位置,id为能延伸到最右端的位置的那个回文子串的中心点位置
 * 
 * @param str 要求解的字符串
 * @return 返回字符串中的最长回文串
 */
public static String longestPlalindromeManacher(String original)
{
	//非空判断
	if((original==null)||original.length()==0)
	{
		return null;
	}
	//将字符串转换为字符数组
	char[] oriArray=original.toCharArray();
	int first=0;
	int end=0;//当前字符串中回文串的始末位置 包括末位置
	
	//对数组做预处理 
	char[] changedArray=new char[oriArray.length*2+3];//一个开始特殊符号  oriArray.length+1个填充符号 一个结尾符号
	int cIndex=0;//修改后数组的遍历下标
	changedArray[cIndex++]='$';//此处特殊符号选择美元符号
	for(int i=0;i<oriArray.length;i++)//为修改后的数组赋值
	{
		changedArray[cIndex++]='#';//填充特殊符号使用井号
		changedArray[cIndex++]=oriArray[i];
	}
	//最后添加#
	changedArray[cIndex++]='#';//cIndex为changeArray的长度
	changedArray[cIndex++]='%';
	
	//开始进行查找
	int[] assistArray=new int[cIndex];//定义等长辅助数组
	int mx=0,id=0;//辅助求解
	int resLen=0,resCenter=0;//回文串长度 中心点位置
	for(int i=1;i<cIndex-1;i++)
	{
		//(╯‵□′)╯︵┻━┻   马拉车太难了
		//核心部分
		if(mx>i)//当前求解位置在已经能够达到的位置之内
		{
			//当前位置的半径为
			//对称位置和半径
			//和 当前距离最右端的距离
			//中小的那一个 
			assistArray[i]=Math.min(assistArray[2*id-i], mx-1);
		}
		else
		{
				assistArray[i]=1;
		}
		//在已有回文串的基础上求解一个最大回文串
		while(changedArray[i+assistArray[i]]==changedArray[i-assistArray[i]])
			assistArray[i]=assistArray[i]+1;
		//判断当前所能到达的最右侧的位置
		if(mx<i+assistArray[i])
		{
			mx=i+assistArray[i];//可以到达为止的下一位置
			id=i;//可以到达最右侧位置的中心点  与最大回文串无直接联系
		}
		//当前求解的最大回文串和存储中的最大回文串 与上一部分的判断并无关联
		if(resLen<assistArray[i])
		{
			resLen=assistArray[i];
			resCenter=i;
		}
	}
	//在改变后数组的中心位置和半径长度 转化为 原数组中的起始点坐标
	first=(resCenter-resLen)/2;
	end=resLen-1;
	//查找结束  将数组转化为字符串返回
	return String.valueOf(oriArray, first, end );
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

没看懂的可以下面提问 ，一天内回复。。。(╯‵□′)╯︵┻━┻

2019-10-20 补个golang动态规划

func longestPlaindromeDynamic(str string)string{
	strLength := len(str)

	if 0 == strLength{
		return ""
	}

	// 字符串转为字符数组
	charArrays := []rune(str)
	// 初始化二维数组
	isPlaindrome := make([][]bool,strLength)
	for i:=0;i<strLength;i++ {
		isPlaindrome[i] = make([]bool,strLength)
	}
	var first,end int

	// 循环遍历字符串
	for i:=0;i<strLength;i++ {
		for j:= 0 ;j<=i;j++ {
			if i-j<2 {
				isPlaindrome[i][j] = charArrays[i]==charArrays[j]
			} else {
				isPlaindrome[i][j] = (charArrays[i] == charArrays[j]) && isPlaindrome[i-1][j+1]
			}

			if isPlaindrome[i][j] && (end-first)<(i-j){
				end = i
				first = j
			}
		}
	}

	return string(charArrays[first:end+1])
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34