Leetcode 5 Longest Palindromic Substring

思路1

中心扩展法。遍历整个数组，每次选取一个字符作为中心字符，然后每次分为奇数和偶数两种情况进行扩展。使用一个max记录最大长度，便于计算最长的substring的起止点。在得到奇数和偶数情况下的两个长度odd与even后，分别比较其与max之间的大小关系，计算并记录起点。最后通过max和起点start信息可以计算出最长的substring。

复杂度分析

时间复杂度O($x^2$), 空间复杂度O(1)

代码

class Solution {
    // expand around centerpublic String longestPalindrome(String s) {
    int maxLength = 0, start = 0;for(int i = 0; i < s.length(); i++) {
    // assume the length is oddint oddLength = find(s,i,i);if(oddLength > maxLength) {
    maxLength = oddLength;start = i - maxLength/2;}// assume the length is evenint evenLength = find(s,i,i+1);if(evenLength > maxLength) {
    maxLength = evenLength;start = i+1 - maxLength/2;}}return s.substring(start,start+maxLength);}public int find(String s, int left, int right) {
    int len = 0;while(left >= 0 && right <= s.length()-1) {
    if(s.charAt(left) == s.charAt(right)) {
    len += (left == right) ? 1 : 2;left--;right++;}else break;}return len;}
}

思路2

动态规划。状态转移方程：dp[start][end] = true iff. dp[start+1][end-1] == true && s[start] == s[end]
在循环中，外层循环枚举长度，内层循环枚举起点。使用start和max记录全局起点和最大长度，方便返回正确的字符串。dp变量初始化的时候将所有长度为1的标记为true，然后检查长度为2的，符合条件的标记为true；最后再循环检查长度为3以上的。

复杂度分析

时间复杂度O($x^2$), 空间复杂度O($x^2$)

代码

public class Solution {
    /*** @param s: input string* @return: the longest palindromic substring*/public String longestPalindrome(String s) {
    // write your code hereif (s == null || s.length() == 0) {
    return "";}int n = s.length();int start = 0, max = 1;boolean[][] dp = new boolean[n][n];for (int i = 0; i < n; i++) {
    dp[i][i] = true;}// length = 2for (int i = 0; i < n - 1; i++) {
    if (s.charAt(i) == s.charAt(i + 1)) {
    dp[i][i + 1] = true;max = 2;start = i;}}// length > 2for (int i = 3; i <= n; i++) {
    for (int j = 0; j <= n - i; j++) {
    if (dp[j + 1][j + i - 2] && s.charAt(j) == s.charAt(j + i - 1)) {
    dp[j][j + i - 1] = true;if (i > max) {
    max = i;start = j;}}}}return s.substring(start, start + max);}
}