1. 本题知识点

动态规划

2. 题目描述

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

输入：

s = "cbbd"

输出：

"bb"

3. 解题思路

首先找子串，设置左右边界，移动边界找子串

判断子串是否回文，使用 boolean 类型的二维数组记录是否回文
```
a...ai   j
```
```
dp[i,j] = s[i]==s[j] && s[i+1]==s[j-1]
```

4. 代码

public class Solution {
       public String longestPalindrome(String s) {
           int length = s.length();        if (length == 0) {
               return "";        }        String maxStr = s.substring(0, 1);        boolean[][] dp = new boolean[length][length];        // 遍历数组        for (int right = 1; right < length; right++) {
               for (int left = 0; left < right; left++) {
                   // 两端不相等，即不回文                if (s.charAt(left) != s.charAt(right)) {
                       continue;                }                // 两端相等，即回文                if (left + 1 >= right - 1) {
                       // 两端相邻                    dp[left][right] = true;                } else {
                       dp[left][right] = dp[left + 1][right - 1];                }                // 设置回文串                if (dp[left][right] && right - left + 1 > maxStr.length()) {
                       maxStr = s.substring(left, right + 1);                }            }        }        return maxStr;    }}

转载地址：http://ncjvb.baihongyu.com/

你可能感兴趣的文章