Leetcode — Top Interview 150–125. Valid Palindrome

It’s an easy problem with description being:

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

1 <= s.length <= 2 * 105

s consists only of printable ASCII characters.

Following what’s a palindrome, you basically remove all non-alpha then call to lower the case method and make a revert to compare.

Using methods and a bit of reg exp you can solve this in 3 lines:

class Solution {
    public boolean isPalindrome(String s) {
        final String reduced = s.replaceAll("[^A-Za-z0-9]", "").toLowerCase();
        final String inverted = new StringBuilder(reduced).reverse().toString();
        return reduced.equals(inverted);
    }
}

Runtime: 15 ms, faster than 22.51% of Java online submissions for Valid Palindrome.

Memory Usage: 44.8 MB, less than 34.15% of Java online submissions for Valid Palindrome.

That should be enough as simple and easy question, but to have it better performance you could iterate and check each char and remove and adapt as needed, for this case checkout saksham answer on leetcode (if you wish me to explain in details, please comment down bellow).

—

That’s it! If there is anything thing else to discuss feel free to drop a comment, if I missed anything let me know so I can update accordingly.

Until next post! :)