5. Longest Palindromic Substring

本文给出了Leetcode第5题的代码。

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.
Example:

Input: “cbbd”

Output: “bb”

自己写的代码：
参照了： http://blog.csdn.net/hopeztm/article/details/7932245

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
public class Solution {
	public char[] preProcess(String s){
        int n = s.length();
        if(n == 0){
            char[] ch1 = new char[2];
            ch1[0] = '^';
            ch1[1] = '$';
            return ch1;
        }else{
            char[] ch2 = new char[n+n+3];
            int curIndex = 0;
			ch2[curIndex++] = '^';
            for(int i = 0;i < n; i++){
                ch2[curIndex++] = '#';
                ch2[curIndex++] = s.charAt(i);
            } 
            ch2[curIndex++] = '#';
            ch2[curIndex++] = '$';
            return ch2;
        }
    }
    
    public String longestPalindrome(String s) {
        char[] ss = preProcess(s);
        int n = ss.length;
        int[] p = new int[n];
        int cntrl = 0;
        int right = 0;
        for(int i = 1;i < n - 1;i++){
            int i_mirror = cntrl + cntrl - i;
            p[i] = (right > i) ? Math.min(right - i,p[i_mirror]) : 0;
            
            while(ss[i + p[i] + 1] == ss[i - p[i] - 1])
                p[i]++;
                
            if(i + p[i] > right){
                cntrl = i;
                right = i + p[i];
            }
        }
        
        int maxLen = 0;
        int indexOfCntrl = 0;
        for(int i = 1; i < n - 1;i++){
            if(p[i] > maxLen){
                maxLen = p[i];
                indexOfCntrl = i;
            }
        }
        return s.substring((indexOfCntrl - maxLen - 1)/2,(indexOfCntrl + maxLen - 1)/2);
    }
}

另外还有比这个简介的多的代码：

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
public class Solution {
    public String longestPalindrome(String s) {
    if(s==null){
        return "";
    }
   char[] arr = s.toCharArray();
	  int max = 0;
	  int maxi = 0;
	  int maxj = 0;
	  
	  for(int i = 0; i< arr.length;){
		  int i1 = getFarestSameElementIndex(arr,i);
		  int dist = getDistance(arr,i,i1);
		  int index1 = i-dist;
		  int index2 = i1 + dist;
		  int l = index2 - index1;
		  if(l>max){
		          max = l;
			  maxi = index1;
			  maxj = index2;
		  }
		  i = i1+1;
	  }
	  
	  return s.substring(maxi, maxj+1);
}
private int getDistance(char[] arr,int index1,int index2){
	int i1 = index1-1;
	int i2 = index2+1;
	int dist = 0;
	while(i1>=0&&i2<arr.length){
		if(arr[i1]==arr[i2]){
			dist++;
		}else{
			break;
		}
		i1--;i2++;
	}
	return dist;
}
private int getFarestSameElementIndex(char[] arr, int index){
	for(int i = index+1;i<arr.length;i++){
		if(arr[i]!=arr[index]){
			return i-1;
		}
	}
	return arr.length-1;
}
}
本文总阅读量次.

留言

▲