5. Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/?envType=featured-list&envId=top-google-questions

input :

• s

output :

• 가장 긴 palindromic 부분 문자열을 출력하시오.

조건 :

• s는 숫자, 영문자로 이루어져 있다.

---

Solution explain : Solution1

idea

substring의 길이를 1 ~ len(s)까지 만들면서 가장 큰 것부터 내려오며 확인을 한다.
입력 값의 최대 길이가 1000이므로 최대 1,000,000의 연산이 수행되어 괜찮은 듯 하다.

DP : DP approach from geeksforgeeks

주의

• 파이썬의 경우 문자열을 뒤집는 방식이 있으므로 이를 활용하자.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        for i in range(len(s), -1, -1):
            start = 0
            while start + i <= len(s):
                temp = s[start: start + i]
                rev_temp = temp[::-1]

                if temp == rev_temp:
                    return temp
                start += 1

# s = Solution()
# print(s.longestPalindrome("babad"))
# print(s.longestPalindrome("cbbd"))