Monday, June 3, 2024
 Popular · Latest · Hot · Upcoming
184
rated 0 times [  189] [ 5]  / answers: 1 / hits: 21977  / 9 Years ago, thu, november 12, 2015, 12:00:00

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 for loop from:



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:



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

More From » algorithm

 Answers
4

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 os, and then move to both ns.



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





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




[#64420] Tuesday, November 10, 2015, 9 Years  [reply] [flag answer]
Only authorized users can answer the question. Please sign in first, or register a free account.
mckinleykeyshawnb

Total Points: 281
Total Questions: 99
Total Answers: 111

Location: Saudi Arabia
Member since Sat, Aug 20, 2022
2 Years ago
;