LeetCode #125 Valid Palindrome Solution & Explanation

This problem can be divide into two parts: removing non-alphanumeric characters and checking whether the phrase is a palindrome or not.

LeetCode Problem

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.


Solution

In this problem, we can divide it into two parts.

We can remove non-alphanumeric characters by using ascii code to check.

C# Solution

Solution1

public class Solution {
    public bool IsPalindrome(string s) {
        //1.remove non-alphanumeric characters
        List<char>list = new List<char>();
        
        s = s.ToLower();

        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9'))
            {
                list.Add(c);
            }
        }

        //2.check if Palindrome or not
        for(int i=0;i<list.Count/2;i++)
        {
            if(list[i] != list[list.Count-1-i]) 
            {
                return false;           
            }
        }
        return true;                   
    }
}

Solution2 – built-in function char.IsLetterOrDigit

public class Solution {
    public bool IsPalindrome(string s) {
        //1.remove non-alphanumeric characters
        List<char>list = new List<char>();
        
        s = s.ToLower();

        for (int i = 0; i < s.Length; i++)
        {
            char c = s[i];
            if (char.IsLetterOrDigit(c))
            {
                list.Add(c);
            }
        }

        //2.check if Palindrome or not
        for(int i=0;i<list.Count/2;i++)
        {
            if(list[i] != list[list.Count-1-i]) 
            {
                return false;           
            }
        }
        return true;                   
    }
}

We can utilize a built-in function to substitute the ASCII code checking for alphanumeric characters.

Java Solution

Solution1

class Solution {
    public boolean isPalindrome(String s) {
        //1.remove non-alphanumeric characters
        List<Character> list = new ArrayList<>();

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {
                list.add(c);
            }
        }

        //2.check if Palindrome or not
        for (int i = 0; i < list.size() / 2; i++) {
            if (list.get(i) != list.get(list.size() - 1 - i)) {
                return false;
            }
        }

        return true;
    }
}

Runtime : 4ms、4ms、5ms ≈ faster than 50%~60%

Solution2 – built-in function Character.isLetterOrDigit

class Solution {
    public boolean isPalindrome(String s) {
        //1.remove non-alphanumeric characters
        List<Character> list = new ArrayList<>();

        s = s.toLowerCase();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isLetterOrDigit(c)) {
                list.add(c);
            }
        }

        //2.check if Palindrome or not
        for (int i = 0; i < list.size() / 2; i++) {
            if (list.get(i) != list.get(list.size() - 1 - i)) {
                return false;
            }
        }

        return true;
    }
}

Runtime : 6ms、5ms、5ms ≈ faster than 50%~60%

Python3 Solution

Solution1

class Solution:
    def isPalindrome(self, s: str) -> bool:
        list = []

        s = s.lower()

        for c in s:
            if (c >= 'a' and c <= 'z') or (c >= '0' and c <= '9'):
                list.append(c)

        for i in range(len(list) // 2):
            if list[i] != list[-1 - i]:
                return False

        return True

Solution2 – built-in function isalnum

class Solution:
    def isPalindrome(self, s: str) -> bool:
        list = []

        s = s.lower()

        for c in s:
            if c.isalnum():
                list.append(c)

        for i in range(len(list) // 2):
            if list[i] != list[-1 - i]:
                return False

        return True

JavaScript Solution

Solution1

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function(s) {
    let arr = [];
    
    s = s.toLowerCase();
    
    for (let i = 0; i < s.length; i++) {
        let c = s.charAt(i);
        if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9')) {
            arr.push(c);
        }
    }
    
    for (let i = 0; i < arr.length / 2; i++) {
        if (arr[i] !== arr[arr.length - 1 - i]) {
            return false;
        }
    }
    
    return true;
};

Conclusion

In this problem, we can easily remove non-alphanumeric characters by using ascii code or built-in functions.

Regarding checking for a palindrome phrase, we have already discussed and found a solution in the previous posts.

🧡If my solution helps, that is my honor!

🧡You can support me by clicking some ad or sharing my posts, thanks a lot

If you got any problem about the explanation, please feel free to let me know

The problem link : Valid Palindrome – LeetCode

Random post

Leave a Reply

Your email address will not be published. Required fields are marked *