05. 求最长回文子串

题目：

提交01：目标先实现功能

 1 class Solution {
 2     public String longestPalindrome(String s) {
 3        char[] ch = s.toCharArray();
 4         if(ch.length==0){
 5             return "";
 6         }
 7         int left = 0;
 8         int right = 0;
 9         int index = 0;
10         int j =0;
11         int k=0;
12         for(int i=1;i<ch.length;i++){
13             while(index<i){
14                 for(j=index,k=0;j<=i-k;j++,k++){
15                     if(ch[j] != ch[i-k]){
16                         break;
17                     }
18                 }
19                 if(j>=i-k){
20                     if(i-index>right-left) {
21                         left = index;
22                         right = i;
23                     }
24                 }
25                 index++;
26             }
27            index = 0;
28         }
29 
30         StringBuffer stringBuffer = new StringBuffer();
31         while(left<=right) {
32             stringBuffer.append(ch[left]);
33             left++;
34         }
35         return stringBuffer.toString();
36     }
37 }

很明显，耗时太严重，现在考虑如何优化？？

提交02：优化

 1 class Solution {
 2     
 3     public String longestPalindrome(String s) {
 4         if(s==null||s.equals("")){
 5             return "";
 6         }
 7         int low =0;
 8         int high =0;
 9         int tempLow =0;
10         int tempHigh = 0;
11         char[] ch = s.toCharArray();
12         for(int i=0;i<ch.length;i++){
13             tempLow = i;
14             tempHigh = i;
15             while(tempHigh<ch.length-1&&ch[tempHigh+1]==ch[tempLow]){
16                 tempHigh++;
17             }
18             //i=tempHigh;
19             while(tempLow>0&&tempHigh<ch.length-1&&ch[tempLow-1]==ch[tempHigh+1]){
20                 tempLow--;
21                 tempHigh++;
22             }
23             if(high-low<tempHigh-tempLow){
24                 high = tempHigh;
25                 low = tempLow;
26             }
27             
28         }
29         return s.substring(low,high+1);
30         
31     }
32 }

当讲 i = tempHigh 放开后

提交：03

 1 class Solution {
 2     
 3     public String longestPalindrome(String s) {
 4         if(s==null||s.equals("")){
 5             return "";
 6         }
 7         int low =0;
 8         int high =0;
 9         int tempLow =0;
10         int tempHigh = 0;
11         char[] ch = s.toCharArray();
12         for(int i=0;i<ch.length;i++){
13             tempLow = i;
14             tempHigh = i;
15             while(tempHigh<ch.length-1&&ch[tempHigh+1]==ch[tempLow]){
16                 tempHigh++;
17             }
18             i=tempHigh;
19             while(tempLow>0&&tempHigh<ch.length-1&&ch[tempLow-1]==ch[tempHigh+1]){
20                 tempLow--;
21                 tempHigh++;
22             }
23             if(high-low<tempHigh-tempLow){
24                 high = tempHigh;
25                 low = tempLow;
26             }
27             
28         }
29         return s.substring(low,high+1);
30         
31     }
32 }

极大的缩短了执行时间。

提交04 ：优化

使用数组保存状态具有轻微优化

 1 class Solution {
 2     
 3     public String longestPalindrome(String s) {
 4         if(s==null||s.equals("")){
 5             return "";
 6         }
 7         int[] index = new int[2];
 8         int tempLow =0;
 9         int tempHigh = 0;
10         char[] ch = s.toCharArray();
11         for(int i=0;i<ch.length;i++){
12             tempLow = i;
13             tempHigh = i;
14             while(tempHigh<ch.length-1&&ch[tempHigh+1]==ch[tempLow]){
15                 tempHigh++;
16             }
17             i=tempHigh;
18             while(tempLow>0&&tempHigh<ch.length-1&&ch[tempLow-1]==ch[tempHigh+1]){
19                 tempLow--;
20                 tempHigh++;
21             }
22             if(index[1]-index[0]<tempHigh-tempLow){
23                 index[1] = tempHigh;
24                 index[0] = tempLow;
25             }
26             
27         }
28         return s.substring(index[0],index[1]+1);
29         
30     }
31 }

05. 求最长回文子串

题目：

提交01： 目标先实现功能

提交02： 优化

提交：03

提交04 ： 优化

提交01：目标先实现功能

提交02：优化

提交04 ：优化