最长回文子串-数据结构与算法(中)

当前位置:　首页>> 技术小册>> 数据结构与算法(中)

**难度: Medium**

> 内容描述

```
给定一个字符串s，找出s中最长的回文子字符串。你可以假设s的最大长度为1000。

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

```

## 解题方案

> 思路 1
******- 时间复杂度: O(n^2)******- 空间复杂度: O(n^2)******

使用动态规划的思路,用一个二维数组cache[i][j]记录i到j是否为回文串, beats 54.36%

```java
class Solution {
    // 采用动态规划
    // 如果 i == j ，则只有一个字母 肯定是回文串
    // 如果 char[i] == char[j] && j == i + 1 , 两个字母相等 肯定是回文串
    // 如果 char[i] == char[j] && j > i + 1 && cache[i+1][j-1]为true，则肯定是回文串
    public String longestPalindrome(String s) {
        if(s == null || s.length() <2){
            return s;
        }
        boolean[][] cache = new boolean[s.length()][s.length()]; // 记录 i ~ j 是否是回文串
        char[] chars = s.toCharArray();
        int len = s.length();
        int start = 0;
        int end = 0;
        // 采用至底向上的动态规划，也可以采用递归方式
        for(int i = len - 1; i >= 0; i --){
            for(int j = i; j < len; j ++){
                if(i == j){
                    cache[i][j] = true;    
                }else if(j == i + 1 && chars[i] == chars[j]){
                    cache[i][j] = true;
                    if(end - start + 1 < 2){
                        end = j;
                        start = i;
                    }
                }else if(chars[i] == chars[j] && cache[i + 1][j-1]){
                    cache[i][j] = true;
                    if(end - start  < j-i){
                        start = i;
                        end = j;
                    }
                }else{
                    cache[i][j] = false;
                }
            }
        }
        return s.substring(start,end+1);
    }
}
```

该分类下的相关小册推荐：

编程之道-算法面试(下)

数据结构与算法之美

数据结构与算法(上)

业务开发实用算法精讲

算法面试通关 50 讲

编程之道-算法面试(上)

数据结构与算法(下)