[파이썬 알고리즘 인터뷰] 가장 킨 팰린드롬

github.com/onlybooks/algorithm-interview

 

유니코드 이야기.

초기 문자표현 방식은 아스키였다. 아스키코드는 그러나 1바이트에 모든 문자를 표현했다. 1비트는 체크섬으로 제외하고 7비트(128글자)로 표현했었다. 이러다보니 한글이나 한자같은 2개이상의 특수문자를 합쳐 표현해 오류가 발생할때가 있었다.

이를 해결하고자 넉넉한 2~4바이트 공간을 가진것이 유니코드였다. 그러나 유니코드는 메모리를 쓸때없이 잡아먹었다.

이를 해결하고자 가변길이의 인코딩 방식인 UTF-8이 사용된 것이다.

필요하면 개발하면 됩니다

파이썬3은 실제 내부적으론 UTF-8 인코딩을 사용하지 않는다.

 

아 우리 그런거 안해요 

만약 문자열을 UTF-8로 인코딩하면 인덱스를 이용한 접근 시 각 문자마다 바이크 길이가 달라져 전체 문자열을 스캔하지 않는 이상 빠른 접근이 불가능하기 때문이다.

그래서, 파이썬은 문자열 단위로 다른 고정 길이 인코딩 방식을 사용한다.

if 모든 문자열 in 아스키 범위:

    Latin-1 인코딩(고정 1바이트)

elif 특수 기호, 그림 이모티콘, 희귀 언어 등:

    UCS-4(고정 4바이트)

else:

   UCS-2(고정 2바이트)

---

5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd" Output: "bb"

 

---

 

Longest Palindromic Substring - LeetCode

 

투포인터를 이용해서 풀 수 있다. 

투포인터(홀수, 짝수) 를 이용해 점점 확장(두 문자가 같을때까지)하면서 비교를 진행한다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left:int, right:int)->str:
            while left >=0 and right <= len(s) and s[left] == s[right-1]:
                left -=1
                right +=1
            return s[left+1:right-1]
        
        if len(s)<2 or s==s[::-1]:
            return s
            
        result = ''
        for i in range(len(s)-1):
            result = max(result,
                         expand(i, i+1),
                         expand(i, i+2),
                         key = len)
        return result

---

 

그냥 똑같은 문제다. 코드 그대로 써도 len만 추가하면된다... 뜨악 😌

코딩테스트 연습 - 가장 긴 팰린드롬

 

def solution(s):
    def expand(left:int, right:int)->str:
        while left >=0 and right <= len(s) and s[left] == s[right-1]:
            left -=1
            right +=1
        return s[left+1:right-1]

    if len(s)<2 or s==s[::-1]:
        return len(s)

    result = ''
    for i in range(len(s)-1):
        result = max(result,
                     expand(i, i+1),
                     expand(i, i+2),
                     key = len)
    return len(result)