LeetCode - 最长回文子串
同样是三年前做的一道题目，很经典的字符串领域的算法题，求字符串的最长回文子串，当时我也是提交了好几次，并且看了相关的资料以后，才成功通过。
原题地址： https://leetcode-cn.com/problems/longest-palindromic-substring/
题目描述：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。示例 2：
输入: "cbbd"
输出: "bb"解题思路：
关于求字符串的最长回文子串，其实网上已经有很多的解释了，我这边简单说下我当时的一个解法和结果。
一共有两个StringBuilder，分别表示最长回文子串和当前的子串；
从s的第0个字符到第n个字符开始遍历，每次求以第i个和第i, i+1字符为中心，向两边发散着求回文字符串；
找到一个回文字符串之后，判断当前的回文字符串长度是否比最长的回文字符串更长，如果更长，将result设置为当前的回文字符串。
其实下面这段代码还存在可以优化的点，比如StringBuilder不用替换了，每次直接新建个就好了，简单粗暴。
个人题解：
public String longestPalindrome(String s) {
if (s.isEmpty()) {
return s;
}
StringBuilder result = new StringBuilder();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
sb.replace(0, sb.length(), getPalindromic(s, i, i));
if (sb.length() >= result.length())
result.replace(0, result.length(), sb.toString());
sb.replace(0, sb.length(), getPalindromic(s, i, i + 1));
if (sb.length() >= result.length())
result.replace(0, result.length(), sb.toString());
}
return result.toString();
}
private String getPalindromic(String str, int l, int r) {
while (l >= 0 && r < str.length()) {
if (str.charAt(l) != str.charAt(r)) {
break;
} else {
l--;
r++;
}
}
return str.substring(l + 1, r);
}结果：
再次成功超越53.79%的用户...
