[리트코드] 125. Valid Palindrome

문제

https://leetcode.com/problems/valid-palindrome/

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 * 10**5
• s consists only of printable ASCII characters.

---

✔ 문제접근 #1 순차탐색[통과] ⭕

Intuition
정규표현식을 통하여 유효한 문자를 찾고, 순차탐색을 통하여 팰린드롬인지 확인한다.

Algorithm
정규표현식으로 알파벳 그리고 숫자를 찾는다.

전체 문자열을 탐색하며 대문자라면 모두 소문자로 바꿔준다.

마지막으로 문자열 절반을 탐색하며 앞뒤가 같은지 확인해준다.

def isPalindrome(self, s: str) -> bool:
    # 정규 표현식을 통해 원하는 문자만 골라서 리스트로 변환한다.
    regex = r'[a-zA-Z0-9]'
    result = re.findall(regex, s)

    # 문자중 모든 대문자를 소문자로 변환한다. # O(n)
    for i in range(len(result)):
        elem = result[i]
        if elem.isupper():
            result[i] = elem.lower()

    # 팬린드롬인지 확인한다. # O(n)
    n = len(result)
    for i in range(n//2):
        if result[i] != result[n-1-i]:
            return False
    return True

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • 정규표현식을 통한 str문자열 찾기 평균 O(N)
  • 소문자로 변환 O(N)
  • 팬린드롬 확인 O(N)
  • 그러므로 전체시작복잡도 : O(N)

• 공간복잡도 : O(N)
  
  • 정규표현식 활용을 위한 result배열사용

---

기타풀이 및 회고

전체적으로 전처리과정은 문자열길이가 10**5로 길지 않기 때문에 많은사람들이 비슷하게 풀이를 한 것 같다. 팰린드롬을 판단하는 과정은 for문이 아니라 아니라 투포인터를 활용해서 절반만 탐색하도록 하는 방법도 있었다.