Palindrome Check

Problem

Write a function that determines whether or not a given a string of characters is a palindrome

A palindrome is defined as a string that is written the same forward as backward

Code

Python

def isPalindrome(string):
reversedString = ""
for i in reversed(range(len(string))):
reversedString += string[i]
return string == reversedString

JavaScript

function isPalindrome(string) {
let reversedString = '';
for (let i = string.length - 1; i >= 0; i--) {
reversedString += string[i];
}
return string === reversedString;
}
​
exports.isPalindrome = isPalindrome;

TypeScript

export function isPalindrome(string: string) {
let reversedString = '';
for (let i = string.length - 1; i >= 0; i--) {
reversedString += string[i];
}
return string === reversedString;
}

Java

class Program {
public static boolean isPalindrome(String str) {
String reversedString = "";
for (int i = str.length() - 1; i >= 0; i--) {
reversedString += str.charAt(i);
}
return str.equals(reversedString);
}
}

C++

using namespace std;
​
bool isPalindrome(string str) {
string reversedString = "";
for (int i = str.length() - 1; i >= 0; i--) {
reversedString += str[i];
}
return str == reversedString;
}

Space-Time Complexity

TimeSpace
WorseO(n2)O(n)

Where n is the length of the input string

When we build our reversed string and do reversedString += string[i], at each iteration in the for loop, we're rebuilding a new string. In most languages where strings are immutable, if you do new += string[i], adding a character to a string, you're actually re-creating the entire new string, iterating through every character in new, and adding string[i]; This is an O(n)-time operation. Since we're performing an O(n)-time operation at each iteration in the for loop, this will turn our function into an O(n2)-time algorithm overall

Notes

solution 1

Create a new string that's going to be the reversed version of our input string, compare that new string with the input string, and see if they're equal to each other

To do this we'll create a variable called reversedString, initialize it to the empty string, then iterate through the reversed version of our given string, meaning we'll start at the last index of our string and go all the way to index zero

At every point in the iteration, we'll build the reversedString by adding the letter at index i in the given string, reversedString += string[i]

Once we're done building the reversed string, we'll do the palindrome comparison by testing weather or not our given string is equal to the reversed string we just built, return string == reversedString

solution 2

Instead of creating a new string, let's just store everything in a list, an array, and at the end we join the list into one string and do the palindrome comparison

To do this instead of initializing reversedString to an empty string, we'll initialize it to an empty list, an empty array, reversedChars, and when we do our iteration backwards through the given string, instead of saying reversedString += string[i], we'll say reversedChars.append(string[i]), or .push or whatever it is in your language of choice. This will keep pushing our string letters into the array, and at the very end instead of returning reversedString == string[i] we'll return "".join(reversedChars) == string

solution 3

This will be the recursive way to solve this problem, it won't be a better solution that solution 2, but it'll be a different approach

Notice that when you're looking at a string and you want to know if it's a palindrome, you basically ask if the first letter is equal to the last letter, and if the string in the middle, the substring, is a palindrome as well. By applying this logic and approaching the problem in this way, assuming we have an isPalindrome() function, we can solve this problem recursively

In our calling function, isPalindrome() apart from taking in a string we can also take in the first index that we're looking at in the recursive call, i

To dynamically calculate j the last index that we're looking at, at each recurisve call we can say, j = len(string) - 1 - i

Our base case will be whenever we arrive at the middle of our string or we're past the middle point, we'll just return i >= j. Otherwise, return true if the first letter is equal to the last letter, and isPalindrome() called on the string in the middle is true, return string[i] == string[j] and isPalindrome(mid). We can show off our recursive skills and do both of these checks in one line, return True if i >= j else string[i] == string[j] and isPalindrome(string, i + 1)

solution 4

This solutiuon will involve an iterative approach. The idea is that we've come up with algorithms that take O(n)-time, and it's obvious that we're not going to do better than that. We have to iterate through our given string to determine if it's a palindrome. But, as we've seen in solution 3, we don't have to store a new string and use recursion that might end up using additional space

To do this we initialize two pointers, one at our first letter and another pointer at our last letter. We then compare both letters, and if they're equal to each other we keep moving towards the middle of the string, otherwise we don't have a palindrome and we return false. If the pointers overlap then we're done, return true

In the actual implementation we'll first initialize the left pointer at the first index, leftIdx = 0, and initialize the right pointer at the last index, rightIdx = len(string) - 1

Then, while our left pointer comes before the right pointer, while leftIdx < rightIdx, if the two letters at both pointers are not equal to each other, if string[leftIdx] != string[rightIdx], return false, return False. Otherwise, if both letters are equal to each other, then increment the left pointer, leftIdx += 1, and decrement the right pointer, rightIdx -= 1

Once you get to the point where both pointers point to the same letter, in an odd string, or are past each other, in an even string, then you're out of the while loop and you're dealing with a palindrom so you're officially done, return True

Edit this page