# 125. Valid Palindrome > [!META]- Inline Metadata > [tags:: #career #concepts/programming/algorithms/two-pointers ] > [project group:: Neetcode 150] > [difficulty:: easy] > [status:: done] > [link:: https://leetcode.com/problems/valid-palindrome/] > [up:: [[Leetcode MOC]]] ## 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_. ### 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. ## Solution ### Mine #### Python ```python def valid_palindrome(s: str) -> bool: s = re.sub("[^a-zA-Z0-9]+", "", s) s = s.lower() j = len(s) - 1 for i in range(len(s)): if s[i] != s[j]: return False j -= 1 return True ``` This uses two pointers. Another alternative for Python only is reversing the string using list slicing: ```python def valid_palindrome_2(s: str) -> bool: s = re.sub("[^a-zA-Z0-9]+", "", s) s = s.lower() return s == s[::-1] ``` This uses the same memory (probably due to the regex) but is slightly slower. #### Rust ### LC's ## Things I Learned In Regex `\w` matches `[a-zA-Z0-9_]` ## Scratchpad Filtering: `re.sub("\W+", "", s)` Lower: `s = s.lower()` Idea would be to run two pointers at either end of the filtered string, and if at any point they're not equal in value, return false