[LeetCode]5.最长回文子串

题目描述
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1:

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

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

分析
刚开始拿到这道题的时候,感觉毫无头绪,如果采用暴力破解的话,时间复杂度是O(n3),有点太高了。后来网上搜了一些文章,提到可以用动态规划的方法。因为一个字符天然是一个回文串,而两个字符只要相同,那它们在一起也构成一个回文串。而以此类推,三个字符的串只要首尾两个字符相同就是回文串。继续往上推,如果一个字符串,它处于首尾两个字符之间的子串是回文串,并且它的首尾字符相同,则它就是一个回文串。因此只需要用一个二维数组,第一维是字符串的第一个字符的下标,第二维是尾字符的下标。用这样一个二维数组来缓存结果,就可以在枚举输入字符串的所有子串的时候,根据之前缓存的结果快速地判断当前的子串是否是回文串。

实现代码如下

class Solution {

public String longestPalindrome(String s) {
    char[] in = s.toCharArray();
    int stringLen = s.length();
    boolean[][] len = new boolean[stringLen][stringLen];
    int start = 0;
    int end = 0;
    for(int i = 0; i < stringLen; i++) {
        for(int j = 0; j < stringLen - i; j++) {
            if(i == 0) {
                len[j][j] = true;
            } else if(i == 1) {
                if(in[j] == in[j + 1]) {
                    len[j][j + 1] = true;
                }
            } else {
                if(in[j] == in[j + i] && len[j + 1][j + i - 1]) {
                    len[j][j + i] = true;
                }
            }
            if(len[j][j + i] == true) {
                start = j;
                end = j + i;
            }
        }
    }
    return s.substring(start, end + 1);
}

}

评论

暂无评论