Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/125.html

125	Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

@tag-string

Algorithm

Only need to establish two pointers, left and right, to traverse the entire string from the beginning and the end of the character respectively.

  • If a non-alphanumeric character is encountered, it will be skipped and the search will continue until the next alphanumeric or end is found.
  • or continue to traverse, if it encounters an uppercase letter, convert it to lowercase. When both the left and right pointers find alphanumeric characters, compare these two characters,
    • if they are equal, continue to compare the following two alphanumerics found separately,
    • if not equal, return false

Pitfall

  1. Replace() did not add All at the beginning, if it is not replaceAll(), it is pure char matching, and has nothing to do with regex

Therefore, you must replaceAll() to match regex

  1. Regex: ^ should be placed inside the parentheses, not outside the parentheses, otherwise ^ will not work, and then delete everything you want to leave
		[abc]	Find any character between the brackets
		[^abc]	Find any character NOT between the brackets
		[0-9]	Find any digit between the brackets
		[^0-9]	Find any digit NOT between the brackets
		(x|y)	Find any of the alternatives specified

Code

  • 
public class Valid_Palindrome {

	public class Solution {
	    public boolean isPalindrome(String s) {
	                if (s.length() == 0) {
	            return true;
	        }

	        // regex to keep only chars
	        s = s.replaceAll("[^a-zA-Z0-9]", ""); // replace non-characters with empty, i.e. remove them

	        s = s.toLowerCase();

	        int i = 0;
	        int j = s.length() - 1;
	        while (i <= j) {
	            if (s.charAt(i) != s.charAt(j)) {
	                return false;
	            }

	            i++;
	            j--;
	        }

	        return true;

	    }
	}

}

  • // OJ: https://leetcode.com/problems/valid-palindrome/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size();
        while (i < j) {
            while (i < j && !isalnum(s[i])) ++i;
            while (i < j && !isalnum(s[j])) --j;
            if (i < j && tolower(s[i++]) != tolower(s[j--])) return false;
        }
        return true;
    }
};

  • class Solution(object):
  def isPalindrome(self, s):
    """
    :type s: str
    :rtype: bool
    """
    start, end = 0, len(s) - 1
    while start < end:
      if not s[start].isalnum():
        start += 1
        continue
      if not s[end].isalnum():
        end -= 1
        continue
      if s[start].lower() != s[end].lower():
        return False
      start += 1
      end -= 1
    return True

All Problems

All Solutions