5.Longest-Palindromic-Substring

5. Longest Palindromic Substring

题目地址

https://leetcode.com/problems/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;
  }

}