Valid palindrome.
Given an input string. We have to write a code to check if it is a palindrome, considering only alphanumeric characters and ignoring cases.
Note: For this problem, consider the empty string as a valid palindrome.
For Example –
Example 1:
Input: “A man, a plan, a canal: Panama”
Output: true
Explanation: After removing non-alphanumeric characters, the string is amanaplanacanalpanama. So, it’s a palindrome
Example 2:
Input: “race a car”
Output: false
Before solving this problem, Let’s first understand what is Palindrome?
Palindrome
A palindrome is a word, phrase, or sequence that reads the same backward as forwards. For example – Nitin, madam, etc.
We have to consider two important points while solving this problem. First, we have to consider only alphanumeric characters and second, we have to ignore cases when we compare two characters.
Also, at the end of this post, I have shared a video tutorial link to this problem. We have discussed the problem statement. Let’s discuss how we can solve this problem.
Programming questions on string
Valid palindrome video tutorial
Another variation of this problem is valid palindrome ii.
Valid Palindrome – Java Code
We can solve this problem using two pointers. The idea here is to traverse a string from both ends using two pointers. Here are the steps:
- Declare two variables start and end. Initialize start and end variables with 0 and string length minus one.
- Run a loop and start comparing characters present at the start and end index. We have to compare characters only if it is alphanumeric. To ignore the case let’s convert them into lowercase.
- If both the characters are not equal then return false, else increment the value of start variable and decrement the value of end variable.
The time complexity of this approach is O(n) and its space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//Valid Palindrome Java Code public boolean isPalindrome(String s) { //Declare two variables int start = 0; int end = s.length()-1; //Run a loop while(start <= end) { //If it is not a alphanumeric character, increment start count while(start < end && !Character.isLetterOrDigit(s.charAt(start))) start++; //If it is not a alphanumeric character, decrement end count while(start < end && !Character.isLetterOrDigit(s.charAt(end))) end--; //If it is not equal, return false if( start < end && Character.toLowerCase(s.charAt(start)) != Character.toLowerCase(s.charAt(end))) return false; start++; end--; } return true; } |
