转载

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

原文 https://segmentfault.com/a/1190000018025326

正文到此结束