字符串中最长的回文

问题描述 投票：0回答：10

我编写了以下函数来查找字符串中最长的回文。它工作正常，但不适用于“中午”或“更红”等单词。 我摆弄并更改了 

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

更新： 在保罗给出了很棒的答案之后，我认为为了清晰起见，更改这两个变量是有意义的：

var oddPal  = centeredPalindrome(i-1, i + 1);
var evenPal = centeredPalindrome(i, i+1);
javascript algorithm palindrome
10个回答
9
投票

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

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

示例（使用 

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")
);

1
投票

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

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

链接到 要点

动态规划的使用。将每个问题分解为自己的方法，然后将每个问题的解决方案加在一起以获得答案。

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();
0
投票

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

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;
    }
0
投票
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"));
0
投票

    let str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
    let rev = str.split("").reverse().join("").trim();
    let len = str.length;
    let a="";
    let result = [];
    for(let i = 0 ; i < len ; i++){
        for(let j = len ; j > i ; j--){
            a = rev.slice(i,j);
            if(str.includes(a)){
                result.push(a);
                break;
            }
        }
    }
    result.sort((a,b) => { return b.length - a.length})
    let logPol = result.find((value)=>{
        return value === value.split('').reverse().join('') && value.length > 1
    })

    console.log(logPol);

0
投票
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
0
投票

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("n"));

这将给出错误的输出，因此在只有一个字符的情况下需要注意这种情况。

0
投票

const str = "更红"; 让 maxStr = "";

  for (let i = 0; i < str.length; i++) {
    let longStr = "";
    longStr += str[i];

    for (let j = i + 1; j < str.length; j++) {
      longStr += str[j];
      if (
        longStr.split("").reverse().join("") === longStr &&
        longStr.length > maxStr.length
      ) {
        maxStr = longStr;
        break;
      }
    }
  }

  console.log("maxStr:", maxStr);
-1
投票
 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;
            }
        }
    }
-4
投票
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
最新问题
© www.soinside.com 2019 - 2025. All rights reserved.