Today I'm going to be talking through my evaluation of a problem, exploration of a solution, and the route to finding it.
The problem was finding the longest palindrome in a string.
As an aside, a palindrome is a series of letters, or characters, that can be flipped at their center point and remain exactly the same. "mom" flipped is "mom", so it's a palindrome. "dog" flipped is "god" which is its own weirdness, but isn't a palindrome. "poop" is also a palindrome.
Okay, so I know I need to find words that are identical going left as they are going right. Breaking that down, I really just need to see if the character to the left is the same as the character to the right. Which is as simple as using "===". But what about selecting those characters. Well, if I can start in the middle of a word, then I'd just need to move left at the same pace I move right. I can do that with a for loop, just using my iterator as plus for one side and a minus for the other.
Great. So what about saving the result, so I can compare it to any other palindrome I find? Well, I can just declare a variable. This could take the form an array. If we did that, we'd be able to hold all of the potential palindromes we found. Of course, we only need the longest one. So we could just save the longest one as a string. And, if we find a longer one later, we can simply use .length to compare them, and overwrite our variable with the longer one if necessary.
Using a string is pretty effective too, because as we do each check, iterating out, we can simply add both letters to each side of our current string and save it, assuming both chars are equal.
Now, depending on how you've been thinking about this along with me, you may have used your solution for an even or an odd palindrome. What I've said so far applies to both, but there is an important distinction between them. When we check for an even length palindrome, we want to start by comparing the first two characters and moving out. But with an odd palindrome, the center character will always equal itself. Just think about the example of "Wow". There's no need to check on the "o" here, so we can give it a buy really. As such, we really have two distinct starting points, for every run of our loop. And different logic follows from those starting points. It might be easiest for us to simply write two seperate loops, one for odd palindromes and one for even. And to keep code legible, it would behoove us to simply make each their own "helper" function.
//even palindrome checker
const evenPalindrome = function(string, startPoint) {
let palindrome = '';
//in case to the left isn't even a palindrome
if(string[startPoint] !== string[startPoint + 1]){
return palindrome;
} else {
palindrome = string[startPoint] + string[startPoint + 1];
}
for(let i = 1; i < string.length; i++){
const right = string[startPoint + i + 1];
const left = string[startPoint - i];
if (right === left && right !== undefined && left !== undefined){
palindrome = right + palindrome + left;
} else {
break;
}
}
return palindrome;
};
//odd palindrome checker
const oddPalindrome = function(string, startPoint){
let palindrome = '';
palindrome += string[startPoint];
for(let i = 1; i < string.length; i++){
const right = string[startPoint + i];
const left = string[startPoint - i];
//if the left and right are equal and not undefined
if (right === left && right !== undefined && left !== undefined){
palindrome = right + palindrome + left;
} else {
break;
}
}
return palindrome;
};
Now that we've done that, we still have the problem of starting points. We simply don't know where in the string the center of the longest palindrome will be. But computers are really fast. For our purposes, we can afford to try every single starting point. If we do, there's no way we will miss our palindrome. So, in our main function we can simply loop over the string we're given, and for each potential starting point, aka each index of the string, we can run both of our helper functions. if their returns are ever larger then the palindrome we have stored right now, we'll simply replace it.
var longestPalindrome = function(string) {
//i string
//o string
//c white space is valid
//e empty string should return empty string
let longestPal = '';
for(let i = 0; i < string.length; i++){
let oddPal = oddPalindrome(string, i);
let evenPal = evenPalindrome(string, i);
if (oddPal.length > longestPal.length){
longestPal = oddPal;
} else if (evenPal.length > longestPal.length){
longestPal = evenPal;
}
}
return longestPal;
};
//should loop over string, taking each character index as a possible center point of a palindrome
//At each center point, have to check three styles of palindrome
//odd style
//even style, left as center mate
//even style, right as center mate
With this, we've reasoned out how to solve what may have appeared a daunting problem at first. If I had to give one piece of advice to anyone struggling with learning code, it would be K.I.S.S. Keep it simple stupid.
By starting with the simplest parts of the problem, and solving out from those, you'll be able to solve anything. But before you can start solving, you have to stop being overwhelmed by the problem as a whole. My solution to this problem ended up being overly complex and inefficient, but it was a solution. And its starting point was really as simple as the problem of find a palindrome can be. Lets compare one letter, to the other, and see if they match. The truth is, there's no magic to solving problems in programming. I believe the best and worst problem solvers can all reach the same solution. The best thing you can do though, to reach it faster, is to ground yourself. Find the smallest part you can conceive of solving, and build out. Take one problem on at a time, whether than worrying about solving the whole thing at once. If you have ideas for later parts, great, accomadate them. But don't let your fear of running into road blocks on later parts of the problem get in your way from starting a solution.
Just like with blogs, and really writing anywhere, the hardest part of coding is often times the very first words you write. So take what you can wrap your brain around, and start writing. You'll start finding solutions much faster than you expected. And remember Keep It Simple, Stupid.
Solution:
//even palindrome checker
const evenPalindrome = function(string, startPoint) {
let palindrome = '';
//in case to the left isn't even a palindrome
if(string[startPoint] !== string[startPoint + 1]){
return palindrome;
} else {
palindrome = string[startPoint] + string[startPoint + 1];
}
for(let i = 1; i < string.length; i++){
const right = string[startPoint + i + 1];
const left = string[startPoint - i];
if (right === left && right !== undefined && left !== undefined){
palindrome = right + palindrome + left;
} else {
break;
}
}
return palindrome;
};
//odd palindrome checker
const oddPalindrome = function(string, startPoint){
let palindrome = '';
palindrome += string[startPoint];
for(let i = 1; i < string.length; i++){
const right = string[startPoint + i];
const left = string[startPoint - i];
//if the left and right are equal and not undefined
if (right === left && right !== undefined && left !== undefined){
palindrome = right + palindrome + left;
} else {
break;
}
}
return palindrome;
};
var longestPalindrome = function(string) {
// Your code here
//i string
//o string
//c white space is valid
//e empty string should return empty string
let longestPal = '';
for(let i = 0; i < string.length; i++){
let oddPal = oddPalindrome(string, i);
let evenPal = evenPalindrome(string, i);
if (oddPal.length > longestPal.length){
longestPal = oddPal;
} else if (evenPal.length > longestPal.length){
longestPal = evenPal;
}
}
return longestPal;
};
//should loop over string, taking each character index as a possible center point of a palindrome
//At each center point, have to check three styles of palindrome
//odd style
//even style, left as center mate
//even style, right as center mate
Top comments (0)