Java: Decide if a String is a Palindrome
This post is part of my ongoing Interview Guide in which I document my journey to land a software engineering position.
This post walks you through the creation of a Java function that decides if a given string is a palindrome or not.
Problem: Given a String, write a function that returns TRUE if the string is a palindrome and FALSE if it doesn’t.
Solution: All a palindrome is is a string that is the same reversed as it is when the characters are arranged normally. Therefore, all we have to do is check whether the characters of the first half of the string match with the characters of the last half.
We know that Java’s String class provides a .charAt(int index) function that returns the character value of the character at a given position in the string. Therefore, we can construct a function that has two pointers, one at the beginning index of the string and one at the last index of the string. Then we can simply increment and decrement each pointer respectively, checking if the character at both indices are equal, until the pointers meet in the middle (or are separated by an index of one).
Here’s what the code looks like:(https://gist.github.com/SIRHAMY/723ba939652abba2d53d)
We can see that the algorithm will run in O(n/2) time – as it must compare at most n/2 characters – which simplifies to O(n).