|:-------------|:-------------|:-------------|

|2|[Add Two Numbers][002]|Linked List, Math|

|3|[Longest Substring Without Repeating Characters][003]|Hash Table, Two Pointers, String|

|5|[Longest Palindromic Substring][005]|String|

|8|[String to Integer (atoi)][008]|Math, String|

|15|[3Sum][015]|Array, Two Pointers|

|17|[Letter Combinations of a Phone Number][017]|String, Backtracking|

Given a string**s**, find the longest palindromic substring in**s**. You may assume that the maximum length of**s** is 1000.

**Example:**

**Example:**

**Tags:** String

题意是寻找出字符串中最长的回文串，所谓回文串就是正序和逆序相同的字符串，也就是关于中间对称。我们先用最常规的做法，依次去求得每个字符的最长回文，要注意每个字符有奇数长度的回文串和偶数长度的回文串两种情况，相信你可以很轻易地从如下代码中找到相关代码，记录最长回文的始末位置即可，时间复杂度的话，首先要遍历一遍字符串，然后对每个字符都去求得最长回文，所以时间复杂度为O(n^2)。

classSolution {

int st, end;

publicStringlongestPalindrome(Strings) {

int len= s.length();

if (len<=1)return s;

char[] chars= s.toCharArray();

for (int i=0; i< len; i++) {

helper(chars, i, i);

helper(chars, i, i+1);

}

return s.substring(st, end+1);

}

privatevoidhelper(char[]chars,intl,intr) {

while (l>=0&& r< chars.length&& chars[l]== chars[r]) {

--l;

++r;

}

if (end- st< r- l-2) {

st= l+1;

end= r-1;

}

}

}

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]

[title]:https://leetcode.com/problems/longest-palindromic-substring

[ajl]:https://github.com/Blankj/awesome-java-leetcode

packagecom.blankj.medium._005;

publicclassSolution {

intst,end;

publicStringlongestPalindrome(Strings) {

intlen =s.length();

if (len <=1)returns;

char[]chars =s.toCharArray();

for (inti =0;i <len;i++) {

helper(chars,i,i);

helper(chars,i,i +1);

}

returns.substring(st,end +1);

}

privatevoidhelper(char[]chars,intl,intr) {

while (l >=0 &&r <chars.length &&chars[l] ==chars[r]) {

--l;

++r;

}

if (end -st <r -l -2) {

st =l +1;

end =r -1;

}

}

publicstaticvoidmain(String[]args) {

Solutionsolution =newSolution();

System.out.println(solution.longestPalindrome("babad"));

System.out.println(solution.longestPalindrome("cbbd"));

}

}