[LeetCode]5.Longest Palindromic Substring

신동재·2021년 9월 15일
0

코딩테스트 준비

목록 보기
6/8

리트코드 코딩 테스트 준비
https://leetcode.com/problems/longest-palindromic-substring/
문제에 대한 자세한 설명은 다음 사이트에서 확인 할 수 있다.

❓ 문제

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

❗ 접근 방법

문자열의 값을 계속 비교해나가면서 거꾸로 뒤집은 문자열과 길이가 같을때 max_length값 보다 크면 계속 업데이트 해주면서 가장 긴 문자 를 찾는다.

⭕ 내가 작성한 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        a = Counter(s)
        sub_str = ""
        flag = 1
        answer = ""
        for i in range(len(a)) :
            if a[i] != 1 :
                flag = 0
                break
        if flag == 1 :
            return 1
        else :
            for i in range(len(s)) :
                sub_str = ""
                for j in s[i:] :
                    sub_str = sub_str + j
                    if sub_str == sub_str[::-1] and len(answer) < len(sub_str) :
                        answer = sub_str
                
        return answer
                
            
            

💯 다른사람이 풀이한 코드

class Solution:  
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        maxLen = 0
        ans = ""
        for i in range(n):
            # 길이가 홀수인 palindrome 조사
            left, right = i, i
            while True:
                if (left >= 0 and right < n) and s[left] == s[right]:
                    if maxLen < right - left + 1:
                        maxLen = right - left + 1
                        ans = s[left:right+1]
                    left -= 1
                    right += 1
                else:
                    break
            
            # 길이가 짝수인 palindrome 조사
            left, right = i, i+1
            while True:
                if (left >= 0 and right < n) and s[left] == s[right]:
                    if maxLen < right - left + 1:
                        maxLen = right - left + 1
                        ans = s[left:right+1]
                    left -= 1
                    right += 1
                else:
                    break
        
        return ans

🧑🏻 후기

내가 푼 코드는 시간제한이 걸렸다. 큰 인풋 값을 넣으면 O(n2)로는 무리인거 같다.

다른사람이 풀이한 코드를 보면서 작성하였다.
다시 풀어봐야겠다..

profile
Software Developer / 1997.12.05

0개의 댓글