06. Longest Palindromic Substring

🎯 leetcode - 5. Longest Palindromic Substring

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 6번 문제
- 가장 긴 팰린드롬(회문) 부분 문자열을 출력하시오.

📌 날짜

2020.01.16

📌 시도 횟수

1 try

💡 Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        for i in range(len(s)):
            for j in range(i + 1):
                if self.isPalindrome(s[j : len(s) - i + j]):
                    return s[j : len(s) - i + j]

    def isPalindrome(self, s):
        return s[:] == s[::-1]

💡 문제 해결 방법

- 가장 긴 팰린드롬 문자열을 추출하는 것이므로 문자열의 최대 길이 부분 문자열부터 시작했다.
- 가장 긴(전체) 문자열부터 시작해 문자열의 길이를 1개씩 줄여가며 팰린드롬임을 판별한다.
- 만약 가장 먼저 팰린드롬이 참이 되면 프로그램을 종료하고 해당 문자열을 return 한다.

*문자열의 길이 한 개씩 줄이는 방법
- 예를들어 길이가 5인 문자열이 있을 때 위의 사진처럼 범위를 조정할 수 있다.
- 문자열의 인덱스가 (0~4 → 0~3,1~4 → 0~2,1~3,2~4 → ...)임을 보고 인덱스 간의 규칙을 찾아냈다.
  ⊙ 바깥 for문의 i는 0 ~ len(s)-1까지의 값을 가지고,
  ⊙ 안쪽 for문의 j는 0 ~ i 까지의 값을 갖는다.
  ⊙ 따라서 위 i, j에 대하여 문자열의 인덱스는 (j ~ len(s)-1-i+j)의 범위를 가진다.
  ⊙ 즉 이를 문자열 슬라이싱으로 나타내면 s[j : len(s) - i + j] 이다.

💡 새롭게 알게 된 점

- 

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. 투 포인터가 중앙을 중심으로 확장하는 형태

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 and s == s[::-1]: # 해당 사항이 없을 때는 빠르게 리턴해버린다.
            return s
            
        result = "" # result에는 계속해서 가장 긴 팰린드롬이 갱신되어 저장될 것임

        for i in range(len(s) - 1):
            # expaned(i, i+1)는 홀수 팰린드롬 판단, expaned(i, i+2)는 짝수 팰린드롬 판단
            result = max(result, expand(i, i + 1), expand(i, i + 2), key=len)
        return result

💡 새롭게 알게 된 점

✔ 기본형 : max(iterable) 
- 매개변수 : 반복이 가능한 자료형 
- 반환형 : 매개변수로 들어온 인자 내부에서 제일 큰 값을 반환한다.

✔ 응용형 : max(iterable1, iterable2, ...)
- 매개변수 : 반복이 가능한 자료형`들`
- 반환형 : 매개변수로 들어온 반복이 가능한 인자들 중에 가장 큰 인자(덩어리)을 반환한다.
여기서 반환형은 iterable1내부에 가장 작은 값이 아니라, iterable1 과 iterable2 중 큰 것을 반환한다.
- key를 지정해줄 수 있다. (예를 들어서 (key = len)으로 설정하면 길이를 기준으로 최댓값을 반환한다.)
# 출처: https://blockdmask.tistory.com/411 [개발자 지망생]


✔ 투 포인터가 아직은 익숙하지 않은데 앞으로는 이 방법도 구현하기 전에 한번쯤 고려하도록 노력해야겠다~!

---

👀이해가 안된다면 눈으로👀