最長的迴文字符串

我寫了下面的函數來查找字符串中最長的迴文。它工作正常，但不適用於像「中午」或「更紅」的單詞。我擺弄周圍，改變了第一線的for循環來源：最長的迴文字符串

var oddPal = centeredPalindrome(i, i);

到

var oddPal = centeredPalindrome(i-1, i);

，現在它的工作原理，但我不清楚在爲什麼。我的直覺是，如果你正在檢查一個奇數長度的迴文，它將在開始時有一個額外的字符（我將它標出來，這就是我得出的結論）。我的理由是否正確？

var longestPalindrome = function(string) { 

    var length = string.length; 
    var result = ""; 

    var centeredPalindrome = function(left, right) { 
    while (left >= 0 && right < length && string[left] === string[right]) { 
     //expand in each direction. 
     left--; 
     right++; 
    } 

    return string.slice(left + 1, right); 
    }; 

    for (var i = 0; i < length - 1; i++) { 
    var oddPal = centeredPalindrome(i, i); 
    var evenPal = centeredPalindrome(i, i); 

    if (oddPal.length > result.length) 
     result = oddPal; 
    if (evenPal.length > result.length) 
     result = evenPal; 
    } 

    return "the palindrome is: " + result + " and its length is: " + result.length; 
};

UPDATE：保羅真棒answer後，我覺得很有道理更改清晰度兩個變量：

var oddPal = centeredPalindrome(i-1, i + 1); 
var evenPal = centeredPalindrome(i, i+1);

來源

2015-11-12 devdropper87

YES - 那終於有道理了。當然你會爲偶數迴文做i + 1，因爲他們的「中鋒」的賠率是2而不是1。謝謝！ – devdropper87

我認爲這可能更直觀，編輯上面也是：var oddPal = centeredPalindrome（i-1，i + 1）; var evenPal = centeredPalindrome（i，i + 1）; – devdropper87

我只想指出這個問題有一個快速線性時間算法，稱爲[Manacher算法]（https://en.wikipedia.org/wiki/Longest_palindromic_substring）。 – Blastfurnace

你擁有了它向後 - 如果你輸出的「奇」迴文結構（與您修復），你會發現它們的長度甚至相等。

想象一下「中午」，從第一個「o」開始（左和右）。這匹配，然後你移動它們 - 現在你比較第一個「n」和第二個「o」。不好。但隨着解決辦法，你開始比較兩個「o」，然後移動到兩個「n」s。

實施例（與var oddPal = centeredPalindrome(i-1, i);修復）：

var longestPalindrome = function(string) { 
 

 
    var length = string.length; 
 
    var result = ""; 
 

 
    var centeredPalindrome = function(left, right) { 
 
    while (left >= 0 && right < length && string[left] === string[right]) { 
 
     //expand in each direction. 
 
     left--; 
 
     right++; 
 
    } 
 

 
    return string.slice(left + 1, right); 
 
    }; 
 

 
    for (var i = 0; i < length - 1; i++) { 
 
    var oddPal = centeredPalindrome(i, i + 1); 
 

 
    var evenPal = centeredPalindrome(i, i); 
 

 
    if (oddPal.length > 1) 
 
     console.log("oddPal: " + oddPal); 
 
    if (evenPal.length > 1) 
 
     console.log("evenPal: " + evenPal); 
 

 
    if (oddPal.length > result.length) 
 
     result = oddPal; 
 
    if (evenPal.length > result.length) 
 
     result = evenPal; 
 
    } 
 
    return "the palindrome is: " + result + " and it's length is: " + result.length; 
 
}; 
 

 
longestPalindrome("nan noon is redder");

來源

2015-11-12 17:10:08

我不認爲這個代碼檢查空間。因此，例如，如果您運行 'longestPalindrome（「a level b」）;' 您將獲得最長的迴文作爲長度爲7的「level」。 – jmdeamer

雖然超出了（我的閱讀範圍）這個問題。絕對考慮添加自己的答案，以解決問題的這一部分。 –

如果最大回文較早發現這將是最佳的。一旦發現它將退出兩個循環。

function isPalindrome(s) { 
     //var rev = s.replace(/\s/g,"").split('').reverse().join(''); //to remove space 
     var rev = s.split('').reverse().join(''); 
     return s == rev; 
    } 

    function longestPalind(s) { 
     var maxp_length = 0, 
     maxp = ''; 
     for (var i = 0; i < s.length; i++) { 
     var subs = s.substr(i, s.length); 
     if (subs.length <= maxp_length) break; //Stop Loop for smaller strings 
     for (var j = subs.length; j >= 0; j--) { 
      var sub_subs = subs.substr(0, j); 
      if (sub_subs.length <= maxp_length) break; // Stop loop for smaller strings 
      if (isPalindrome(sub_subs)) { 

       maxp_length = sub_subs.length; 
       maxp = sub_subs; 

      } 
     } 
     } 
     return maxp; 
    }

來源

2017-10-16 12:29:39

最長的迴文字符串

回答

相關問題