题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"
示例 3：

输入：s = "a"
输出："a"

解题思路

暴力遍历所有子串，判断其是否是回文串，同时使用一个状态数组，避免重复子串的判断。

// 子串的开头、结尾、长度
public int maxStart;
public int maxEnd;
public int maxLen;

public void solve(int l, int r, char[] arr, int[][] vis) {
    // 当前子串以及 遍历过，直接返回 
    if (vis[l][r] == 1) {
        return;
    }
  
    if (l > r)
        return;
  
    if (l == r) {
        if ((maxStart - maxEnd + 1) > maxLen) {
            maxStart = maxEnd  = l;
            maxLen = 1;
        }
        return;
    }
    
    //  记录回文串判定的左侧与右侧下标
    int s, e;
    int mid = (l + r) / 2;
    
    //  元素数量为奇数个
    if ((r - l) % 2 == 0) {
        s = mid  - 1;
        e = mid + 1;
    } else {  // 元素数量为偶数个
        s = mid;
        e = mid + 1;
    }
    // 字符串在范围内并且是回文串
    while (s >= l && e <= r && arr[s] == arr[e]) {
        s--;
        e++;
    }

    vis[l][r] = 1;
    //  当前整个子串都是回文串，如果长度大于最大长度，记录当前子串
    if (s == l - 1 && e == r + 1) {
        if ((r - l + 1) > maxLen) {
            maxStart = l;
            maxEnd = r;
            maxLen = (r - l + 1);
        }
    } else {
        // 查找子串
        if ((r - l) > maxLen) {
            solve(l, r -  1, arr, vis);
            solve(l + 1, r, arr, vis);
        }
    }
}

public String longestPalindrome(String s) {
    if (s.length() == 1)
        return s;
    
    // 记录遍历数组
    int[][] vis = new int[s.length()][s.length()];
    // 调用方法记录最大子串的位置
    solve(0, s.length() -  1, s.toCharArray(), vis);
    return s.substring(maxStart, maxEnd + 1);
}

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。