先看代碼
|
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; } |
