回文专题 - Githubissues

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"

Example 2: Input: "cbbd" Output: "bb"

中心扩展法

1.思想：

1）将子串分为单核和双核的情况，单核即指子串长度为奇数，双核则为偶数；

2）遍历每个除最后一个位置的字符index(字符位置)，单核：初始low = 初始high = index，low和high均不超过原字符串的下限和上限；判断low和high处的字符是否相等，相等则low++、high++（双核：初始high = 初始low+1 = index + 1）；

3）每次low与high处的字符相等时，都将当前最长的回文子串长度与high-low+1比较。后者大时，将最长的回文子串改为low与high之间的；

4）重复执行2）、3），直至high-low+1 等于原字符串长度或者遍历到最后一个字符，取当前截取到的回文子串，该子串即为最长的回文子串。

2.时间复杂度解释：

遍历字符：一层循环、O(n-1)；

找以当前字符为中心的最长回文子串：嵌套两个独立循环、O(2n*(n-1)) = O(n^2)。

function longestPalindrome( s) {
        if(s.length <= 1)
            return s;
        var carry = {  sub: '', maxLen: 0}
        var n = s.length - 1; //因为i+1, 需要多留一个
        for(var i = 0;i < n;i++){
            findLongestPalindrome(s,i,i,n, carry);//单核回文
            findLongestPalindrome(s,i,i+1,n, carry);//双核回文
        }
        return carry.sub;
    }
    function findLongestPalindrome( s, low, high, n, carry ){
        while (low >= 0 && high <= n){
            if(s[low] == s[high]){
                if(high - low + 1 > carry.maxLen){
                     carry.maxLen = high - low + 1;
                     carry.sub = s.substring(low , high+1);
                }
                low --;//向两边扩散找当前字符为中心的最大回文子串
                high ++;
            } else{
                break;
            } 
        }
    }

更简单的表现形式

function centerExtend(left, right, str) {//单核回文文
            var sub = str[left]
            while (true) {
                var b = str[left];
                var c = str[right];
                if (!b || !c) {
                    break
                }
                if (b === c) {
                    sub = str.substring(left, right + 1)
                    left--
                    right++
                } else {
                    break
                }
            }

            return {
                len: sub.length,
                sub
            }
        }
        function resolve(str) {
            var max = -1
            var maxSub = ''
            for (var i = 0; i < str.length; i++) {
                var a = centerExtend(i, i, str);
                if (a.len >= max) {
                    max = a.len;
                    maxSub = a.sub;
                }
                var b = centerExtend(i, i + 1, str);
                if (b.len >= max) {
                    max = b.len;
                    maxSub = b.sub
                }
            }
            console.log(maxSub)
            return maxSub
        }

        resolve("ABBABB")

RubyLouvre / algorithmbook

回文专题 #13

5. Longest Palindromic Substring

中心扩展法