[문자열 조작] 유효한 팰린드롬

문제: Valid Palindrome

주어진 문자열이 팰린드롬인지 확인한다. 대소문자 구분을 하지 않아도 되므로 전부 소문자로 변환해서 처리할 수 있다. 특수문자는 무시한다.

리스트로 변환

# 1. convert to list


def isPalindrome(s: str) -> bool:
    strs = []
    for char in s:
        if char.isalnum():  # alphabet or number
            strs.append(char.lower())

    # check palindrome
    while len(strs) > 1:
        if strs.pop(0) != strs.pop():  # using pop method
            return False

    return True


if __name__ == "__main__":
    s = input()
    print(isPalindrome(s))

pop 메소드를 이용해 리스트의 앞과 뒤에서 글자를 빼낸 후 둘을 비교한다.

• isalnum()은 영문자, 숫자 여부를 판별하는 함수이다.
• lower()로 모두 소문자로 변환한다.
• pop(0)를 하면 맨 앞의 값을 가져올 수 있다.

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

데크Deque 자료형을 사용하면 속도를 좀 더 높일 수 있다.

# 2. Use Deque
import collections


def isPalindrome(s: str) -> bool:
    # delare deque
    strs: Deque = collections.deque()

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

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


if __name__ == "__main__":
    s = input()
    print(isPalindrome(s))

deque는 pop(0) 대신 popleft() 이다.

• 리스트의 pop(0)는 O(n)인 데 반해, 데크의 popleft()는 O(1)이다.

슬라이싱 사용

정규표현식 공부 필요

# 3. Use Slice
import re


def isPalindrome(s: str) -> bool:
    s = s.lower()

    # using regular expression, filtering unnecessary letters
    s = re.sub("[^a-z0-9]", "", s)

    return s == s[::-1]  # slicing


if __name__ == "__main__":
    s = input()
    print(isPalindrome(s))

정규표현식으로 불필요한 문자를 필터링하고, 슬라이싱 사용해 원래 문자열과 뒤집은 문자열이 같은지 비교를 한다.

• [::-1]을 사용하면 문자열을 뒤집을 수 있다.

C언어

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

bool isPalindrome(char *s)
{
    int bias_left = 0;
    int bias_right = 1;

    int str_len = strlen(s);

    for (int i = 0; i < str_len; i++)
    {
        // handling skip pointer
        while (!isalnum(s[i + bias_left]))
        {
            bias_left++;
            if (i + bias_left == str_len)
                return true;
        }

        while (!isalnum(s[str_len - i - bias_right]))
        {
            bias_right++;
        }

        if (i + bias_left >= str_len - i - bias_right)
            break;

        // check palindrome
        if (tolower(s[i + bias_left]) != tolower(s[str_len - i - bias_right]))
            return false;
    }
    return true;
}

int main(int argc, char **argv)
{
    if (argc < 2)
        printf("No Auguments\n");
    else if (argc == 2)
    {
        if (isPalindrome(argv[1]))
            printf("True\n");
        else
            printf("False\n");
    }
    else
        printf("Wrong Arguments\n");
    return 0;
}

속도

리스트 << 데크 < 슬라이싱

참고 자료

• 파이썬 알고리즘 인터뷰