node.js - JavaScript 算法题求解——最长的回文子字符串？

Question

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, and there exists one
unique longest palindromic substring.

输入字符串 S， 求字符串中最长的回文子字符串，并返回，如输入 dbakokabbbbbbb 返回 bakokab

var longestPalindrdome = function (s) {
    var t = s.split("").join("#");
    var c = 1, e = 0, cs = 0;
    t = "~" + t + "#";

    for (var j = 1, lenj = t.length - 1; j < lenj; j++, c = 1) {
        while (t[j + c] === t[j - c]){
            c++;
        }

        if (c > e) {
            e = c;
            cs = j;
        }

    }

    var result = t.slice(cs - e + 1, cs + e).replace(/#/g, "").replace(/~/g, "");
    return result;
};

求解更快的算法，不知道 200ms 的算法是怎么样的？

测试用例之一：

var s = 'whdqcudjpisufnrtsyupwtnnbsvfptrcgvobbjglmpynebblpigaflpbezjvjgbmofejyjssdhbgghgrhzuplbeptpaecfdanhlylgusptlgobkqnulxvnwuzwauewcplnvcwowmbxxnhsdmgxtvbfgnuqdpxennqglgmspbagvmjcmzmbsuacxlqfxjggrwsnbblnnwisvmpwwhomyjylbtedzrptejjsaiqzprnadkjxeqfdpkddmbzokkegtypxaafodjdwirynzurzkjzrkufsokhcdkajwmqvhcbzcnysrbsfxhfvtodqabvbuosxtonbpmgoemcgkudandrioncjigbyizekiakmrfjvezuzddjxqyevyenuebfwugqelxwpirsoyixowcmtgosuggrkdciehktojageynqkazsqxraimeopcsjxcdtzhlbvtlvzytgblwkmbfwmggrkpioeofkrmfdgfwknrbaimhefpzckrzwdvddhdqujffwvtvfyjlimkljrsnnhudyejcrtrwvtsbkxaplchgbikscfcbhovlepdojmqybzhbiionyjxqsmquehkhzdiawfxunguhqhkxqdiiwsbuhosebxrpcstpklukjcsnnzpbylzaoyrmyjatuovmaqiwfdfwyhugbeehdzeozdrvcvghekusiahfxhlzclhbegdnvkzeoafodnqbtanfwixjzirnoaiqamjgkcapeopbzbgtxsjhqurbpbuduqjziznblrhxbydxsmtjdfeepntijqpkuwmqezkhnkwbvwgnkxmkyhlbfuwaslmjzlhocsgtoujabbexvxweigplmlewumcone';
// 返回：wfdfw

Answer 1

jsfunction fn1(s) {
    var ret = '';
    for (var i = 0, il = s.length; i < il; i++) {
        var tmp = [];
        tmp[i] = s[i];
        for (var indexLeft = i - 1, indexRight = i + 1;
            indexLeft >= 0 && indexRight < il;
            indexLeft--, indexRight++
        ) {
            if (s[indexLeft] !== s[indexRight]) break;
            tmp[indexLeft] = s[indexLeft];
            tmp[indexRight] = s[indexRight];
        }
        tmp = tmp.join('');
        if (tmp.length > ret.length) {
            ret = tmp;
        }
    }

    return ret;
}

function fn2(s) {
    var start = 0, length = 0;
    for (var i = 0, il = s.length; i < il; i++) {
        for (var indexLeft = i - 1, indexRight = i + 1;
            indexLeft >= 0 && indexRight < il;
            indexLeft--, indexRight++
        ) {
            if (s[indexLeft] !== s[indexRight]) break;
        }

        var tmpLength = indexRight - indexLeft - 1;
        if (tmpLength > length) {
            start = indexLeft + 1;
            length = tmpLength;
        }
    }

    return s.substr(start, length);
}

var str = 'dbakokabbbbbbb';

console.time('spend1');
console.log(fn1(str));
console.timeEnd('spend1');

console.time('spend2');
console.log(fn2(str));
console.timeEnd('spend2');

Answer 2

原始代码帮你注释一下

var longestPalindrdome = function (s) {
    var t = s.split("").join("#");  // 第一，说是插，其实不是真的插入，只是写代码的是认为是插入了，而实际代码中不插
    var c = 1, e = 0, cs = 0;
    t = "~" + t + "#";

    for (var j = 1, lenj = t.length - 1; j < lenj; j++, c = 1) {
     /*通过前面的对比获得部分信息的，所以这个 c 可能大于1 C的来源是用这个公式得到的,其中f(i) 就是你说的 c 
      f(i) >= min { f(2j-i),f(j)-2(i-j) } ,for j<=i<= j+f(i)/2 */
        while (t[j + c] === t[j - c]){
            c++;
        }

        if (c > e) {
            e = c;
            cs = j;
        }

    }

    var result = t.slice(cs - e + 1, cs + e).replace(/#/g, "").replace(/~/g, ""); //这句后面那个替换也不需要了
    return result;
};

Answer 3

用 Manacher 算法来动态规划算出最大回文子串。

http://www.starvae.com/?p=212

Answer 4

也不知道我理解得对不对，英文的应该翻译成中文的，代码应该直接贴出来的。

javascriptvar getTheLongestPalindromic = function(str) {
    'use strict'; 
    var subStrs = str.split(" ");
    var palindromics = {};
    // 得到每个单词出现的次数
    for (var i = 0; i < subStrs.length; i++) {
        if ( typeof palindromics[subStrs[i]] === 'undefined') {
            palindromics[subStrs[i]] = 1;
        } else {
            palindromics[subStrs[i]] = palindromics[subStrs[i]] + 1;
        }
    }

    var words = Object.keys(palindromics);
    var longest = '';
    for (var i = 0; i < words.length; i ++) {
        if(palindromics[words[i]] === 1) {
            continue;
        }
        if(words[i].length > longest.length) {
            longest = words[i];
        }
    }
    return longest;
};

var str = 'Given a string S, thisisthelongestword find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.We were unable to charge your credit card for your Unfuddle STACK account titled "pantao" on Friday, 1 May, 2015 because you have not provided complete billing information.You’re invited to sign up for the beta of App Analytics. Be among the first to get insight into how your app is performing. You won’t need any additional code or app updates, and there’s no extra cost. You’ll be able to: See how often customers visit your app’s page on the App Store Find out how many of your users open your app over time Check your app and In-App Purchase sales Create custom campaign thisisthelongestword links and follow the success of your marketing campaigns Understand which websites refer the most users We’re offering access to the App Analytics beta on a first-come, first-served basis. Sign up below and we’ll send you an email as soon as it’s ready for you.';
console.log(getTheLongestPalindromic(str));

运行结果：93ms

Answer 5

答案莫名其妙被踩，已刪除。