125. Valid Palindrome

1. Description

• 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.

2. Example

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.

3. Solution

• Runtime: 5ms
• Time Complexity: O(N)
• 설명
  • s문자열이 없을 경우를 확인한다.
  • 문자열 확인
    • sorted_s에 isalpha()를 사용하여 알파벳인지 확인하는 작업을 한다.
    • sorted_s에 isdigit()를 사용하여 숫자인지 확인하는 작업을 한다.
    • 다 맞을 경우 sorted_s에 추가하고 모두 소문자로 만든다.
  • Two-Pointer로 검사
    • start는 문자열의 처음(시작)
    • end는 문자열의 마지막(끝)
    • s[start] == s[end]를 통해 palindrome인지 확인을 한다.
    • 맞을 경우 start +1, end -1를 하여 다음으로 넘어간다.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if not s:
            return True
        sorted_s = ""
 
        for char in s:
            if char.isalpha() or char.isdigit():
                sorted_s += char
        sorted_s = sorted_s.lower()
 
        start = 0
        end = len(sorted_s) - 1
 
        while start <= end:
            if sorted_s[start] == sorted_s[end]:
                start += 1
                end -= 1
            else:
                return False
        return True

• 📌isalpha()또는 isdigit()을 사용하여 문자열을 검사하는 방법을 까먹지 말자
  • 더 좋은 방법으로 isalnum()를 사용하여 알파벳과 숫자를 확인할 수 있다.

4. What I Learned

References

• Write resources that you helped from