5. Longest Palindromic Substring(Medium)

题目描述

原题

Description:

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”

原题翻译

描述：

给定一个字符串s，找到s中最长的回文子字符串。您可以假设s的最大长度为1000。

例1：

输入: “babad”
输出: “bab”
另外: “ava”也是一个可行的答案。

例2：

输入: “cbbd”
输出: “bb”

解法一

主要思想

用变量i遍历字符串，从第i个字符开始，left，right两个指针分别向左右遍历，求最大回文长度。

运行速度：超过了86.94%的解答。

内存使用：超过了100%的解答。

源码

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() < 2) {
            return s;
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }
    // 使用left和right两指针遍历是否为回文
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

解法二

主要思想

第一名的答案。

运行速度：超过了100%的解答。

内存使用：超过了100%的解答。

源码

public class Solution {
    int len = 0, maxLength = 0, start = 0;
    public String longestPalindrome(String s) {
        char[] arr = s.toCharArray();
        len = s.length();
        if (len <= 1) 
            return s;
        for (int i = 0; i < len; i++) {
            i = helper(arr, i);
        }
        return s.substring(start, start + maxLength);
    }
    // 从k开始向两边遍历
    private int helper(char[] arr, int k) {
        int i = k - 1, j = k;
        while (j < len - 1 && arr[j] == arr[j + 1])
            j++;
        int nextCenter = j++;
        while (i >= 0 && j < len && arr[i] == arr[j]) {
            i--;
            j++;
        }
        if (j - i - 1 > maxLength) {
            maxLength = j - i - 1;
            start = i + 1;
        }
        return nextCenter;
    }
}