Longest Palindromic Substring

发表于

算法：动态规划

题目

URL：https://leetcode-cn.com/problems/longest-palindromic-substring/

1
2
3
4
5
6
7
8
9
10
11
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

分析

Java解法

扩展中心算法

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.Stack;

public class Solution {
    public String longestPalindrome(String s) {
        String longestS=null, curS=null;
        for(int i=0; i<s.length(); ++i) {
            curS = palindrome(s.toCharArray(), i);
            if (null == curS) continue;
            if (null == longestS) longestS = curS;
            else {
                if (longestS.length() <= curS.length()) longestS = curS;
            }
        }
        return (null == longestS) ? "" : longestS;
    }
    public String palindrome(char[] chArr, int index) {
        Stack<Character> stack1 = new Stack<Character>();
        Stack<Character> stack2 = new Stack<Character>();
        int len1=0, len2=0;
        if(index-1>=0 && chArr[index] == chArr[index-1]) {
            for(int i=index-1; i>=0; --i) {
                int delta = index-1-i;
                if(index+delta>=chArr.length) break;
                if(chArr[i] == chArr[index+delta]) {
                    stack1.push(chArr[i]);
                } else {
                    break;
                }
            }
            len1 = stack1.size()*2;
        }
        if(index-2>=0 && chArr[index] == chArr[index-2]) {
            stack2.push(chArr[index-1]);
            for(int i=index-2; i>=0; --i) {
                int delta = index-2-i;
                if(index+delta>=chArr.length) break;
                if(chArr[i] == chArr[index+delta]) {
                    stack2.push(chArr[i]);
                } else {
                    break;
                }
            }
            len2 = stack2.size()*2 - 1;
        }
        // System.out.printf("%d, %d %c \n", len1, len2, chArr[index]);
        if (0==len1 && 0==len2) return String.valueOf(chArr[index]);
        if (len1>len2) {
            char[] res = new char[len1];
            for(int i=0; !stack1.isEmpty(); ++i) {
                char c = stack1.pop().charValue();
                res[i] = res[len1-1-i] = c;
            }
            return String.copyValueOf(res);
        } else {
            char[] res = new char[len2];
            for(int i=0; !stack2.isEmpty(); ++i) {
                char c = stack2.pop().charValue();
                res[i] = res[len2-1-i] = c;
            }
            return String.copyValueOf(res);
        }
    }
    public static void main(String[] args) {
            String s = "ba";
            String ret = new Solution().longestPalindrome(s);
            String out = (ret);
            System.out.print(out);
    }
}

同样解法的代码优化

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
class Solution {
	public String longestPalindrome(String s) {
		if (s == null || s.length() < 1)
			return "";
		int start = 0, end = 0;
		for (int i = 0; i < s.length(); i++) {
			int len1 = expandAroundCenter(s, i, i);
			int len2 = expandAroundCenter(s, i, i + 1);
			int len = Math.max(len1, len2);
			if (len > end - start) {
				start = i - (len - 1) / 2;
				end = i + len / 2;
			}
		}
		return s.substring(start, end + 1);
	}

	private int expandAroundCenter(String s, int left, int right) {
		int L = left, R = right;
		while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
			L--;
			R++;
		}
		return R - L - 1;
	}
}

动态规划的解法

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
public class App {
	public static void main(String[] args) {
		String s = "aba1ab";
		String ret = new Solution().longestPalindrome(s);
		String out = (ret);
		System.out.print(out);
	}
}
class Solution {
	public String longestPalindrome(String s) {
        if(null == s || s.length() <= 1) {
            return s;
        }
        String origin = s;
        String reverse = new StringBuffer(s).reverse().toString();
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for(int i=0; i<length; ++i) {
            for(int j=0; j<length; ++j) {
                if(origin.charAt(i) == reverse.charAt(j)) {
                    if(0==i || 0==j) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i-1][j-1] + 1;
                    }
                }
                if (arr[i][j]>= maxLen) {
                    int beforeRev = length-1 - j;
                    if(arr[i][j]-1+beforeRev == i) {
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd-(maxLen-1), maxEnd+1);
    }
}

Python解法

​