最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

5. Longest Palindromic Substring

XAMPP教程 admin 132浏览 0评论

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;
}
}

转载请注明:XAMPP中文组官网 » 5. Longest Palindromic Substring