Look at the code first
public class MaxHuiWen { public static void main(String[] args) { // TODO Auto-generated method stub String s = "abb"; MaxHuiWen(s); } //1. Output palindrome string public static void MaxHuiWen(String s){ //Storage the length of the string int length = s.length(); //Storage the longest palindrome string String MaxString = ""; //Transize all substrings of the current string for(int i = 0 ; i < length ; i++){ for(int j = i ; j < length + 1 ; j++){ String s1 = s.substring(i , j); //If the current string is a palindrome string and is greater than the length of MaxString, replace the current MaxString if(HuiWen(s1) && s1.length() > MaxString.length()){ MaxString = s1; } //System.out.println(s1); } } //If the length of MaxString is greater than or equal to 2, it means it is a palindrome string if(MaxString.length() >= 2){ System.out.println(MaxString); } else{ System.out.println("No palindrome string"); } } //2. Determine whether the string is a palindrome string public static boolean HuiWen(String s){ boolean flag = true; int length = s.length(); char s1[] = s.toCharArray(); //Fore and after, traverse the string and compare for(int i = 0 , j = length - 1 ; i <= j ; i++ , j--){ if(s1[i] != s1[j]){ flag = false; } } return flag; } }1. Pastoral judgment of strings
Determine whether a string is a palindrome
Problem description, given a string, such as String T="madam"; to determine whether the string is a palindrome
Method 1: 1. Define two string element pointers (note that Java does not have the concept of pointers), int right=T.length()-1; int left=0;
2. That is, left starts from the left, right starts from the right, and compare whether the referred characters are equal in sequence. If they are equal, left++, right--; otherwise, it will be returned directly, not a backdrop.
while(left<right){if(T.charAt(left)!=T.charAt(right)) return false;left++;right--;}return true;Code:
/* * 3: * Palindrome* Problem description: Palindrome, English palindrome, refers to a string that reads the same along and inversely, such as madam, I love me, * Method 1: * Analysis: Use two "pointers" to scan from the beginning and end of the string respectively. If the values pointed by each "pointer" are equal, this is palindrome*/ 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; } Method 2: Pastellar string such as "madam". If you reverse them all, you will still get its own "madam". When comparing the two strings, if they are equal, it is pastellar.
1. Implement a function that inverts strings
/* * Implement the inversion function of a string*/ private String reverse(String str){ String strResult=""; for(int i=str.length()-1;i>=0;i--){ strResult+=str.charAt(i); } return strResult; } 2. For the target string s, first reverse it temp=reverse(s), and then judge temp.equals(s)/** Invert the string, and then compare it with the original string. If it is equal, it is palindrome, otherwise it is not * The algorithm time complexity is O(n)*/public boolean isPalindrome2(String s){String temp=reverse(s);if(s.equals(temp)) return true;elsereturn false;}Two: How to find the maximum palindromic string for a given string
For example, given the string String T="google", how to find its longest palindrome substring "goog"
1. The simplest and most direct idea is to find all substrings of the string, then determine whether each substring is a palindrome, record, compare and find the palindrome of the maximum length. * The algorithm time complexity is O(n^3)
/* * 4, Find the longest palindrome substring* Problem description: Given a string, find the longest palindrome substring among all its substrings, such as a Google string, the longest substring is goog * Analysis: *1, the simplest and most direct idea is: find all substrings of the string, then judge whether each substring is a palindrome, record, compare and find the palindrome of the maximum length* Algorithm time complexity is O(n^3) */ public String longestPalindrome1(String s){ String result=null; String tempString=""; //Define the length of the longest palindrome substring int max=0; //Transfer all elements in the string for(int i=0;i<s.length();i++){ //The array subscript pointer j starts to traverse forward from the string for(int j=s.length()-1;j>i;j--){ //The palindrome tempString=s.subStr(i, j+1); //If tempString is a palindrome substring and its length (j-i+1)>max if(isPalindrome(tempString)&&(j-i+1)>max){ max=j-i+1; result=subString(i, j+1); } } } return result; }2. The second idea is to judge every character T[i] in the string
Even-length substring centered on T[i], T[i+1] is a palindrome
Is an odd-length substring centered at T[i] a palindrome
public String longestPalindrome2(String T){ String result=null; //Storage the length of the maximum palindrome string int max=0; //Travel through each character and judge the parity extension substring with each character as the center for(int i=0;i<T.length();i++){ //Define two array subscript pointers, and the even subsequence sequence centered on 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++; } //If the length of the substring>max, the length of the sub-palindrome string is temporarily stored as the longest sub-palindrome string =(pEnd-1)-(pStart+1)-1=pEnd-pStart-1 if(pEnd-pStart-1>max){ max=pEnd-pStart-1; result=subString(pStart+1, pEnd-1+1); } //From i as the center, determine whether the extended odd sequence is the palindrome string 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; }