企业官网建设流程全解析

题目链接

https://leetcode.cn/problems/longest-palindromic-substring/?envType=study-plan-v2&envId=top-100-liked

思路

这道题我们采用中心拓展法 + 动态规划，所谓的中心拓展法就是选取一个中点，以这个中点为中心同时向左右拓展看每个串是不是回文串以此来找到最长的回文串，但是这里分奇数 / 偶数两种情况，列如：

"aba"：形如这样的串中心是b

"abba"：形如这样的串中心是bb

而动态规划则是，我们在枚举不同中心时会得到不同长度的回文串，我们要维护一个最长回文串长度以及这个串对应的起点

代码

class Solution { //中心拓展法 public String longestPalindrome(String s) { if(s == null || s.length() == 0) return s; int maxLen = 1; int start = 0; for(int i = 0; i < s.length(); i++) { int len1 = extend(s, i, i); //模拟奇数拓展 int len2 = extend(s, i, i+1); //模拟偶数拓展 int curLen = Math.max(len1, len2); if(curLen > maxLen) { maxLen = curLen; //回文串 = 左边一半 + 中点 + 右边一半 start = i - (curLen - 1) / 2; } } return s.substring(start, start + maxLen); } //扩展函数 private int extend(String s, int l, int r) { while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){ l--; r++; } return r - l - 1; //多扩展的一次要减去 } }