5.Longest-Palindromic-Substring

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"

代码

Approach 1: Brute Force

穷举所有的子串,O(Cn^2) = O(n^2), 每次判断字符串是否为回文,复杂度为 O(n), 故总的时间复杂度为 O(n^3), 大数据集下可能 TLE. 仅在最后返回取子串,空间复杂度为 O(1). P.S. 目前仅 Java 对回文判断优化过。
class Solution {
public String longestPalindrome(String s) {
if (s == null || s.isEmpty()) return "";
int sLen = s.length();
int longest = 0, left = 0;
for (int i = 0; i < sLen; i++) {
for (int j = i; j < sLen; j++) {
if (isPalindrome(s, i, j) && j - i + 1 > longest) {
longest = j - i + 1;
left = i;
}
}
}
return s.substring(left, left + longest);
}
private boolean isPalindrome(String s, int left, int right) {
for (int i = left, j = right; i <= j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) return false;
}
return true;
}
}

Approach #2 odd + even

class Solution {
public String longestPalindrome(String s) {
if (s == null || s.isEmpty()) return "";
int sLen = s.length();
int longest = 0, left = 0;
for (int i = 0; i < sLen; i++) {
// odd
int leftIndex = leftPalindromeIndex(s, i, i);
int palindromeLen = 2 * (i - leftIndex) + 1;
if (palindromeLen > longest) {
left = leftIndex;
longest = palindromeLen;
}
// even
leftIndex = leftPalindromeIndex(s, i, i + 1)
palindromeLen = 2 * (i - leftIndex + 1);
if (palindromeLen > longest) {
left = leftIndex;
longest = palindromeLen;
}
}
return s.substring(left, left + longest);
}
private int leftPalindromeIndex(String s, int left, int right) {
for (; left >= 0 && right < s.length(); left--, right++) {
if (s.charAt(left) != s.charAt(right)) break;
}
return left + 1;
}
}