팰린드롬 연결 리스트

234. Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

Input: head = [1,2,2,1] Output: true

Example 2:

Input: head = [1,2] Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

-----------------------------------------------------------------------------------------------------------------------------------

풀이 1. 리스트 변환

 def isPalindrome(self, head: ListNode) -> bool:
     q: List = []

     if not head:
         return True

    node = head
    #리스트 변환
    while node is not None:
        q.append(node.val)
        node = node.next

    #팰린드롬 판별
    while len(q) > 1:
        if q.pop(0) != q.pop():
            return False
    
    return True

풀이 2. 데크를 이용한 최적화

 def isPalindrome(self, head: ListNode) -> bool:
     #데크 자료형 선언
     q: Deque = collections.deque()

     if not head:
         return True

    node = head
    while node is not None:
        q.append(node.val)
        node = node.next

    #팰린드롬 판별
    while len(q) > 1:
        if q.popleft() != q.pop():
            return False
    
    return True

풀이 3. 런너를 이용한 풀이

 def isPalindrome(self, head: ListNode) -> bool:
     rev = None
     slow = fast = head
     #런너를 이용해 역순 연결 리스트 구성
    while fast and fast.next:
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
    if fast:
        slow = slow.next

    #팰린드롬 여부 확인
    while rev and rev.val == slow.val:
        slow, rev = slow.next, rev.next
    return not rev

유효한 팰린드롬

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

주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

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

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.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

-----------------------------------------------------------------------------------------------------------------------------------

풀이 1. 리스트로 변환

def isPalindrome(self, s: str) -> bool:
    strs = []
    for char  in s:
        if char.isalnum():
            strs.append(char.lower())

    # 팰린드롬 여부 판별
    while len(strs) > 1:
        if strs.pop(0) != strs.pop():
            return False

    return True

풀이 2. 데크 자료형을 이용한 최적화

def isPalindrome(self, s:str) -> bool:
    #자료형 데크로 선언
    strs: Deque = collections.deque()

    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    while len(strs) > 1:
        if strs.popleft() != strs.pop():
            return False
    
    return True

풀이 3. 슬라이싱 사용

def isPalindrome(self, s:str) -> bool:
    s = s.lower()
    #정규식으로 불필요한 문자 필터링
    s = re.sub('[^a-z0-9]', '', s)

    return s == s[::-1] #슬라이싱