5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”Output: “bab”Note: “aba” is also a valid answer.Example 2:
Input: “cbbd”Output: “bb”
难度：medium
题目：给定字符串 s, 找出最长回文子串，你可以假定字符串的最大长度为 1000.
思路：基于每个字符当前位置向两边延展判断子串是否为回文，分两种情况，一种是偶数个字符，另一种是奇数个字符。
优化代码：Runtime: 16 ms, faster than 75.08% of Java online submissions for Longest Palindromic Substring.
class Solution {
// assume s must not be null or empty
public String longestPalindrome(String s) {
if (null == s || s.length() <= 1) {
return s;
}

int sLen = s.length();
// left, right, maxLeft, maxRight, maxLen
// 内部多个变量转成数组
int[] metrics = {0, 0, 0, 0, 0};
for (int i = 0; i < sLen; i++) {
// even
metrics[0] = i – 1;
metrics[1] = i;
longestPalindrome(metrics, s);
// odd
metrics[0] = i – 1;
metrics[1] = i + 1;
longestPalindrome(metrics, s);
}

return s.substring(metrics[2], metrics[3] + 1);
}
// 私有方法
private static void longestPalindrome(int[] metrics, String s) {
while (metrics[0] >= 0 && metrics[1] < s.length()
&& s.charAt(metrics[0]) == s.charAt(metrics[1])) {
metrics[0]–;
metrics[1]++;
}
int curLen = metrics[1] – metrics[0] – 1;
if (curLen > metrics[4]) {
metrics[4] = curLen;
metrics[2] = metrics[0] + 1;
metrics[3] = metrics[1] – 1;
}
}
}
未优化代码：Runtime: 59 ms, faster than 40.22% of Java online submissions for Longest Palindromic Substring.
class Solution {
// assume s must not be null or empty
public String longestPalindrome(String s) {
if (null == s || s.length() < 1) {
return s;
}
int sLen = s.length(), maxLen = 1;
String result = s.substring(0, 1);
for (int i = 0; i < sLen; i++) {
// even
int left = i – 1, right = i;
while (left >= 0 && right < sLen && s.charAt(left) == s.charAt(right)) {
left–;
right++;
}
if (right – left – 1 > maxLen) {
maxLen = right – left – 1;
result = s.substring(left + 1, right); // 构造字符串开销，可以用变量记录开始与结束下标
}

// odd
left = i – 1;
right = i + 1;
while (left >= 0 && right < sLen && s.charAt(left) == s.charAt(right)) {
left–;
right++;
}
if (right – left – 1 > maxLen) {
maxLen = right – left – 1;
result = s.substring(left + 1, right);
}
}
return result;
}
}