先看代码
|
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
|
public class MaxHuiWen { public static void main(String[] args) { // TODO Auto-generated method stub String s = "abb"; MaxHuiWen(s); } //1.输出回文串 public static void MaxHuiWen(String s){ //存储字符串的长度 int length = s.length(); //存储最长的回文串 String MaxString = ""; //遍历当前字符串的所有子串 for(int i = 0 ; i < length ; i++){ for(int j = i ; j < length + 1 ; j++){ String s1 = s.substring(i , j); //如果当前字符串为回文串并且大于MaxString的长度，就替换当前MaxString if(HuiWen(s1) && s1.length() > MaxString.length()){ MaxString = s1; } //System.out.println(s1); } } //如果MaxString长度大于等于2，说明是回文串 if(MaxString.length() >= 2){ System.out.println(MaxString); } else{ System.out.println("没有回文串"); } } //2.判断字符串是否为回文串 public static boolean HuiWen(String s){ boolean flag = true; int length = s.length(); char s1[] = s.toCharArray(); //从前，从后，遍历字符串，进行比较 for(int i = 0 , j = length - 1 ; i <= j ; i++ , j--){ if(s1[i] != s1[j]){ flag = false; } } return flag; } } |
一，字符串的回文判断
判断一个字符串是否为回文
问题描述，给定一个字符串，如String T="madam";要判断该字符串是否为回文
方法一：1，定义两个字符串元素指针(注意java没有指针的概念)，int right=T.length()-1 ;int left=0;
2，即left从左边开始，right从右边开始，依次比较所指的字符是否相等，若相等，则将left++，right--；否则，直接返回不是回文
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
while(left<right){if（T.charAt(left)!=T.charAt(right)）return false;left++;right--;}return true; |
代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/* * 3： * 回文判断 * 问题描述：回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如madam、我爱我， * 方法一： * 分析：使用两个"指针"分别从字符串头和尾扫描，若每一个"指针"所指值都相等，这为回文 */ public boolean isPalindrome(String s){ if(s==null) return false; int left=0; int right=s.length()-1; while(left<right){ if(s.charAt(left)!=s.charAt(right)) return false; left++; right--; } return true; } |
方法二：回文字符串如"madam",若将其全部反转，则还是得到其本身"madam",在将两个字符串比较，若相等，则为回文
1，实现一个将字符串反转的函数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/* * 实现一个字符串的反转函数 */ private String reverse(String str){ String strResult=""; for(int i=str.length()-1;i>=0;i--){ strResult+=str.charAt(i); } return strResult; } 2，对于目标字符串s，首先将其反转temp=reverse(s)，然后在判断temp.equals(s)/** 将字符串倒置，再与原字符串进行比较，若相等，则为回文，否则不是* 算法时间复杂度为O(n)*/public boolean isPalindrome2(String s){String temp=reverse(s);if(s.equals(temp))return true;elsereturn false;} |
二：如何求一个给定字符串的最大回文字符串
例如，给定字符串String T="google",如何求其最长的回文子字符串"goog"
1，最简单直接的想法就是：找出字符串的所有子串，然后判断每一个子串是否是回文，并记录，比较求出最大长度的回文，*算法时间复杂度为O(n^3)
|
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
|
/* * 4,求最长回文子串 *问题描述：给定一个字符串求出其所有子串中最长的回文子串，例如google字符串，最长子串为goog *分析： *1，最简单直接的想法就是：找出字符串的所有子串，然后判断每一个子串是否是回文，并记录，比较求出最大长度的回文 *算法时间复杂度为O(n^3) */public String longestPalindrome1(String s){ String result=null; String tempString=""; //定义最长回文子串的长度 int max=0; //遍历字符串中的所有元素 for(int i=0;i<s.length();i++){ //数组下标指针j从字符串后面开始往前遍历 for(int j=s.length()-1;j>i;j--){ //判断每一个字符串时候为回文 tempString=s.subStr( i, j+1); //如果tempString是回文子串并且其长度(j-i+1)>max if(isPalindrome(tempString)&&(j-i+1)>max){ max=j-i+1; result=subString(i, j+1); } } } return result; } |
2，第二种思路就是对于字符串中的每一个字符T[i]，判断
以T[i]，T[i+1]为中心的偶数长度子字符串是回文
T[i]为中心的奇数长度子字符串是否是回文
|
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
|
public String longestPalindrome2(String T){ String result=null; //存放最大回文字符串的长度 int max=0; //遍历每一个字符，以每一个字符为中心判断奇偶扩展子串 for(int i=0;i<T.length();i++){ //定义两个数组下标指针，以i，i+1为中心的偶子序列 int pStart=i; int pEnd=i+1; while(pStart>=0&&pEnd<=(T.length()-1)&&T.charAt(pStart)==T.charAt(pEnd)){ pStart--; pEnd++; } //如果子字符串的长度>max，则暂存为最长子回文串 子回文串的长度=(pEnd-1)-(pStart+1)-1=pEnd-pStart-1 if(pEnd-pStart-1>max){ max=pEnd-pStart-1; result=subString( pStart+1, pEnd-1+1); } //以i为中心，判断扩展奇序列是否为回文串 pStart=i-1; pEnd=i+1; while(pStart>=0&&pEnd<=(T.length()-1)&&T.charAt(pStart)==T.charAt(pEnd)){ pStart--; pEnd++; } if (pEnd-pStart-1>max) { max=pEnd-pStart-1; result=subStrint(T, pStart+1, pEnd-1+1); } } return result; } |
