javascript 字符串中最长的回文

Longest palindrome in a string

提问by devdropper87

I wrote the following function to find the longest palindrome in a string. It works fine but it won't work for words like "noon" or "redder". I fiddled around and changed the first line in the forloop from:

我编写了以下函数来查找字符串中最长的回文。它工作正常，但不适用于“中午”或“更红”之类的词。我摆弄并更改了for循环中的第一行：

var oddPal = centeredPalindrome(i, i);

to

到

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

and now it works, but I'm not clear on why. My intuition is that if you are checking an odd-length palindrome it will have one extra character in the beginning (I whiteboarded it out and that's the conclusion I came to). Am I on the right track with my reasoning?

现在它起作用了，但我不清楚为什么。我的直觉是，如果您正在检查一个奇数长度的回文，它会在开头多出一个字符（我把它写成了白板，这就是我得出的结论）。我的推理是否正确？

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: After Paul's awesome answer, I think it makes sense to change both variables for clarity:

更新：在 Paul 的精彩回答之后，我认为为了清楚起见，更改这两个变量是有意义的：

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

采纳答案by Paul Roub

You have it backwards - if you output the "odd" palindromes (with your fix) you'll find they're actually even-length.

你把它倒过来了——如果你输出“奇数”回文（用你的修复），你会发现它们实际上是偶数长度。

Imagine "noon", starting at the first "o" (left and right). That matches, then you move them both - now you're comparing the first "n" to the second "o". No good. But with the fix, you start out comparing both "o"s, and then move to both "n"s.

想象一下“中午”，从第一个“o”（左右）开始。匹配，然后您将它们都移动 - 现在您将第一个“n”与第二个“o”进行比较。不好。但是通过修复，您开始比较两个“o”，然后移动到两个“n”。

Example (with the var oddPal = centeredPalindrome(i-1, i);fix):

示例（带有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 its length is: " + result.length;
};

console.log(
  longestPalindrome("nan noon is redder")
);

回答by Velu S Gautam

This will be optimal if the largest palindrome is found earlier. Once its found it will exit both loops.

如果更早发现最大的回文，这将是最佳的。一旦找到，它将退出两个循环。

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

回答by Wes Duff

Here is another take on the subject.

这是对这个主题的另一种看法。

• Checks to make sure the string provided is not a palindrome. If it is then we are done. ( Best Case )
• Worst case 0(n^2)

• 检查以确保提供的字符串不是回文。如果是，那么我们就完成了。（最好的情况）
• 最坏情况 0(n^2)

link to gist

链接到 要点

Use of dynamic programming. Break each problem out into its own method, then take the solutions of each problem and add them together to get the answer.

使用动态规划。把每个问题分解成它自己的方法，然后把每个问题的解决方案加在一起得到答案。

class Palindrome {
   constructor(chars){
     this.palindrome = chars;
     this.table = new Object();
     this.longestPalindrome = null;
     this.longestPalindromeLength = 0;

     if(!this.isTheStringAPalindrome()){
      this.initialSetupOfTableStructure();
     }
   }

   isTheStringAPalindrome(){
     const reverse = [...this.palindrome].reverse().join('');
     if(this.palindrome === reverse){
       this.longestPalindrome = this.palindrome;
       this.longestPalindromeLength = this.palindrome.length;
       console.log('pal is longest', );
       return true;
     }
   }

   initialSetupOfTableStructure(){
     for(let i = 0; i < this.palindrome.length; i++){
       for(let k = 0; k < this.palindrome.length; k++){
        this.table[`${i},${k}`] = false;
       }
     }
     this.setIndividualsAsPalindromes();
   }

   setIndividualsAsPalindromes(){
    for(let i = 0; i < this.palindrome.length; i++){
      this.table[`${i},${i}`] = true;
    }
    this.setDoubleLettersPlaindrome();
   }

   setDoubleLettersPlaindrome(){
     for(let i = 0; i < this.palindrome.length; i++){
       const firstSubstring = this.palindrome.substring(i, i + 1);
       const secondSubstring = this.palindrome.substring(i+1, i + 2);
      if(firstSubstring === secondSubstring){
       this.table[`${i},${i + 1}`] = true;

       if(this.longestPalindromeLength < 2){
         this.longestPalindrome = firstSubstring + secondSubstring;
         this.longestPalindromeLength = 2;
       }
      }
     }
     this.setAnyPalindromLengthGreaterThan2();
   }

   setAnyPalindromLengthGreaterThan2(){
     for(let k = 3; k <= this.palindrome.length; k++){
      for(let i = 0; i <= this.palindrome.length - k; i++){
        const j = i + k - 1;
        const tableAtIJ = this.table[`${i+1},${j-1}`];
        const stringToCompare = this.palindrome.substring(i, j +1);
        const firstLetterInstringToCompare = stringToCompare[0];
        const lastLetterInstringToCompare = [...stringToCompare].reverse()[0];
        if(tableAtIJ && firstLetterInstringToCompare === lastLetterInstringToCompare){

          this.table[`${i},${j}`] = true;

          if(this.longestPalindromeLength < stringToCompare.length){
            this.longestPalindrome = stringToCompare;
            this.longestPalindromeLength = stringToCompare.length;
          }
        }
      }
     }
   }

   printLongestPalindrome(){
     console.log('Logest Palindrome', this.longestPalindrome);
     console.log('from /n', this.palindrome );
   }

   toString(){
     console.log('palindrome', this.palindrome);
     console.log(this.table)
   }
 }

 // const palindrome = new Palindrome('lollolkidding');
 // const palindrome = new Palindrome('acbaabca');
 const palindrome = new Palindrome('acbaabad');
 palindrome.printLongestPalindrome();
 //palindrome.toString();

回答by ankit gupta

function longestPalindrome(str){
   var arr = str.split("");
   var endArr = [];

   for(var i = 0; i < arr.length; i++){
       var temp = "";
       temp = arr[i];
       for(var j = i + 1; j < arr.length; j++){
          temp += arr[j];
          if(temp.length > 2 && temp === temp.split("").reverse().join("")){
             endArr.push(temp);
          }
   }
}

var count = 0;
var longestPalindrome = "";
for(var i = 0; i < endArr.length; i++){
   if(count >= endArr[i].length){
     longestPalindrome = endArr[i-1]; 
   }
   else{
      count = endArr[i].length;
   }
 }
 console.log(endArr);
 console.log(longestPalindrome);
 return longestPalindrome;
}

longestPalindrome("abracadabra"));

回答by Dheerendra Dev

function longest_palindrome(s) {
if (s === '') {
    return ''
}
let arr = [];
let _s = s.split('');
for (let i = 0; i < _s.length; i++) {
    for (let j = 0; j < _s.length; j++) {
        let word = _s.slice(0, j + 1).join('');
        let rev_word = _s.slice(0, j + 1).reverse().join('');
        if (word === rev_word) {
            arr.push(word)
        }
    }
    _s.splice(0, 1)
}
let _arr = arr.sort((a, b) => a.length - b.length);
for (let i = 0; i < _arr.length; i++) {
    if (_arr[arr.length - 1].length === _arr[i].length) {
        return _arr[i]
    }
}

}

}

longest_palindrome('bbaaacc') //This code will give you the first longest palindrome substring into the string

longest_palindrome('bbaaacc') //这段代码会给你第一个最长的回文子串到字符串中

回答by Bahruz Balabayov

 public string LongestPalindrome(string s) {
       return LongestPalindromeSol(s, 0, s.Length-1);
 }
 public static string LongestPalindromeSol(string s1, int start, int end)
 {
        if (start > end)
        {
            return string.Empty;
        }
        if (start == end)
        {
            char ch = s1[start];
            string s = string.Empty;
            var res = s.Insert(0, ch.ToString());
            return res;
        }
        if (s1[start] == s1[end])
        {
            char ch = s1[start];
            var res = LongestPalindromeSol(s1, start + 1, end - 1);
            res = res.Insert(0, ch.ToString());
            res = res.Insert(res.Length, ch.ToString());
            return res;
        }
        else
        {
            var str1 = LongestPalindromeSol(s1, start, end - 1);
            var str2 = LongestPalindromeSol(s1, start, end - 1);
            if (str1.Length > str2.Length)
            {
                return str1;
            }
            else
            {
                return str2;
            }
        }
    }

回答by Siddhartha

This is in JS ES6. much simpler and works for almost all words .. Ive tried radar, redder, noon etc. 

const findPalindrome = (input) => {
  let temp = input.split('')
  let rev = temp.reverse().join('')

  if(input == rev){
    console.log('Palindrome', input.length)
  }
}
//i/p : redder
// "Palindrome" 6