5. Longest Palindromic Substring[Medium].md

5. Longest Palindromic Substring[Medium]

---

출처: https://leetcode.com/problems/longest-palindromic-substring/

• 문제

  Given a string s, return the longest palindromic substring in s.
  
   
  
  Example 1:
  
  Input: s = "babad"
  Output: "bab"
  Explanation: "aba" is also a valid answer.
  Example 2:
  
  Input: s = "cbbd"
  Output: "bb"
   
  
  Constraints:
  
  1 <= s.length <= 1000
  s consist of only digits and English letters.
  Accepted
  1,607,691
  Submissions

• 나의 풀이

  class Solution:
  	def longestPalindrome(self, s: str) -> str:
  		answer = s[0]
  		for idx, chr in enumerate(s):
  			c1 , c2 = idx, idx
  			for i in range(idx - 1, -1, -1):
  				if chr == s[i]:
  					c1 = i
  				else:
  					break
  			for i in range(idx + 1, len(s), 1):
  				if chr == s[i]:
  					c2 = i
  				else:
  					break
  			for i in range(len(s)):
  				if c1 - i >= 0 and c2 + i < len(s):
  					if s[c1 - i] == s[c2 + i]:
  						if len(answer) < c2 - c1 + 2 * i + 1:
  							answer = s[c1 - i:c2 + i + 1]
  					else:
  						break
  		return answer

  먼저, answer의 default 값을 input의 맨 첫번째 값으로 한다.

  이유: 최소 1글자는 들어오기 때문에, 아예 겹치는게 없을 땐, 맨 첫번째 글자가 답이므로

  그리고, c1, c2라는 가장자리 변수?를 선언한다.

  예를 들어, abbbba 가 s라면, c1은 두번째 b, c2는 네번째 b가 될 것이고, 그 다음부터 글자가 palindromic 한지 검사해나가는 식이다.