logo标签列表

字符串中最长回文子串

javascriptalgorithmpalindrome
11

我编写了以下函数来查找字符串中最长的回文。它可以正常工作，但对于"noon"或"redder"这样的单词就不起作用了。我尝试了一下，将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;
};

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

answer 
var oddPal  = centeredPalindrome(i-1, i + 1);
var evenPal = centeredPalindrome(i, i+1);
是的 - 终于有意义了。当然，对于偶回文，你会使用i+1，因为它们的“中心”是2而不是奇数的1。谢谢！ - devdropper87
我认为这可能更直观，同时编辑如下：var oddPal = centeredPalindrome(i-1, i + 1);var evenPal = centeredPalindrome(i, i+1); - devdropper87
我只是想指出，这个问题有一个快速的线性时间算法，称为马拉车算法。 - Blastfurnace
9个回答
9
你搞错了 - 如果你输出“奇数”回文（按照你的修正），你会发现它们实际上是偶数长度的。
想象一下“noon”，从第一个“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")
);

我认为这段代码没有检查空格。因此，例如如果你运行longestPalindrome("a level b");您将获得最长的回文“ level”，长度为7。 - jmdeamer
真的，虽然超出了问题的范围（我读到的）。一定要考虑添加自己的答案来解决这个问题的那部分。 - Paul Roub
运行这段代码给了我：回文是：noon，长度为6 - 是否应该改为redder？ - Om Shankar
如上评论所述，它对空格和非空格字符没有区别。它找到了“noon”（前导和尾随空格），长度为6个字符，就像“redder”一样。这是一个应该修复的问题，但与此特定问题无关。 - Paul Roub
这里必须运行循环以减小长度for (var i = 0; i < length - 1; i++) ==> for (var i = 0; i < length; i++) - Prerana
@Prerana 如果我们进行了这个更改，当我们引用 i + 1 元素时会发生什么？ - Paul Roub
1

这里有另一种看待这个主题的方式。

  • 检查提供的字符串是否不是回文。如果是，则完成。（最佳情况）
  • 最坏情况0（n ^ 2）

链接到{{link1：gist}}

使用动态编程。将每个问题分解为自己的方法，然后将每个问题的解决方案相加以获得答案。

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

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

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

欢迎来到StackOverflow！ 请解释你的解决方案。 - Jonathan
1
首先反转字符串并在反转后的字符串上应用操作。使用双重循环迭代字符串。内部循环从反转的字符串中制作子字符串，如“ABCDE”、“ABCD”、“ABC”、“AB”，如果在主字符串中匹配，则将字符串存入数组。迭代所有字符的循环。最后将得到匹配字符串数组。根据长度排列数组，检查回文元素。 - Sachin Devamore
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
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
-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
3
翻译成中文。仅返回翻译后的文本：这更简单，因为您不是在字符串中搜索回文，而只是判断字符串是否是回文。 - bobrobbob
@bobrobbob 嗯，我不太明白，它是如何知道一个单词是否有效的...它只是寻找相似的字符吗？这似乎完全没有用，因为它们实际上都不是单词。 - Seabizkit
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接