5. Longest Palindromic Substring

문제 주소

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

Longest Palindromic Substring - LeetCode

 

 

문제

 

Given a string s, return the longest

palindromic substring : A string is said to be a palindrome if the string read from left to right is equal to the string read from right to left.

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.

 

문제 풀이

 

제일 긴 좌우대칭인 substring 찾으라는 문제임

 

index 넣고 좌우대칭인지 좌랑 우 읽어서 비교하다가 마지막에 slice로 꺼내기로 함

i는 ++

j도 ++

i 부터 j 까지

i - j 비교

i+1 j-1 비교

i + k ≥ j - k 일때

continue;

 

1차시도

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = "";
        temp = "";
        i = 0;
        j = 0;
        for i in range(len(s)):
            for j in range(i,len(s)):
                for k in range(j-i):
                    if(s[i+k] != s[j-k]):
                        break;
                    elif((i+k)>=(j-k)):
                        temp = s[i:j+1]
                        if(len(temp)>len(longest)):
                            longest = temp

        return longest;

Input

s =

"babad"

Output

"bab"

Expected

"bab"

Input

s =

"cbbd"

Output

""

Expected

"bb"

 

j-i면 i,j가 1차이날때 2개 비교하게 계획했는데 1개밖에 안 돌아가는 거 같아서

for k in range(j-i+1):

여기 고쳤더니 되긴 되는데 시간초과됨

temp 넣고 읽는걸 줄여봄

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = "";
        for i in range(len(s)):
            for j in range(i,len(s)):
                for k in range(j-i+1):
                    if(s[i+k] != s[j-k]):
                        break;
                    elif((i+k)>=(j-k)):
                        if((j-i+1)>len(longest)):
                            longest = s[i:j+1]

        return longest;

Time Limit Exceeded 또 뜸

앞에서부터 하나하나 읽으면서 나가니까 너무 느린거 같아서

i는 앞부터 j는 뒤부터 살피면서 제외하는걸 해보고 싶어짐 ㅎ

지금 있는 longest 보다 j-i가 작아지면 살펴볼 필요도 없으니까 패스하고

j를 뒤부터 살피기로 함 ㅎ

큰 범위부터 봐야 큰게 먼저 걸리니까요

 

최종 답안

class Solution:
    def longestPalindrome(self, s: str) -> str:
        longest = "";
        for i in range(len(s)):
            for j in range(len(s)-1,i-1,-1):
                if(j-i+1<=len(longest)):
                    break;
                for k in range(j-i+1):
                    if(s[i+k] != s[j-k]):
                        break;
                    elif((i+k)>=(j-k)):
                        if((j-i+1)>len(longest)):
                            longest = s[i:j+1]

        return longest;