2021-01-19] Longest Palindromic Substring

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3609/

Explore - LeetCode

 

Palindromic substring.. 구글 번역으로 회문 부분문자열.. 무슨 말인지 처음에 이해를 못했다. ( 영어실력의 부족.. )

그냥 '일요일', '토마토', '이효리' 마냥 앞으로 읽어도, 뒤로 읽어도 같은 문자열을 의미하는 것이다.

 

 

문제 예시 1-4

주어지는 문자열 s에 대해서 위에서 언급한 회문 부분문자열 중 가장 긴 값을 구하는 문제이다.

 

예시 1번처럼 'babad' 는 답이라고 할수있는 값이 'bab','aba'  두 개이다. 이 중 아무거나 반환해주면 된다.

 

문자열이 1개(예시 4)이거나 회문 부분문자열이 없는 경우(예시 5) 첫번째 문자를 반환해주면 된다.

 

주어진 예시에서 없는 내용의 예시로 하나를 들자면,

 

'abaaba' 가 주어진다면, 회문 부분문자열은 총 4개 'aa','aba','baab','abaaba'가 될 것이고,

답으로 가장 긴 값인 'abaaba'를 반환하면 된다.

 

위의 예제로 좀 더 코딩에 가깝게 고민해본다면, 회문 부분문자열은 앞뒤의 문자가 동일해야한다.

 

첫번째 값 'a'로 회문부분문자열이 만들어질려면, 우선 'a'가 또 있어야만 한다. 즉 'a' 와 'baaba'에서

'a' 가 존재하는 지를 판단해야한다. 만약 존재하지 않는다면 'a'로 만들수 있는 회문 부분문자열은 없다.

if 'a' in 'baaba':
    # 회문 부분문자열 검사 가능
else:
    # 할필요 없으니 pass

그리고 'a'가 여러 개가 존재할 수 있으므로, 모든 부분에 대해서 검사해야한다.

( 'aba' , 'abaa', 'abaaba' ) 해당 문자열이 회문 부분문자열이 될 수 있는지 검사해야하는 대상이다.

 

모든 부분에 대해서 검사해야하지만, 우리는 가장 큰 값을 원하기 때문에 맨 뒤에서 부터 검사하여,

값이 구해진다면 앞의 작은 문자열들은 검사할 필요가 없어진다. ( 코딩에서 종단조건으로 쓰여진다. )

 

res_list = [idx for idx, value in enumerate('baaba') if value == 'a']
# 'a'를 가지고 있는 index 값을 List로 만들어 주는 코드
res_list.reverse()
# 만들어진 List를 역순으로 만들어야 맨 뒤에서 부터 검사할 수 있다.

 

이제 'abaaba' 를 먼저 회문 부분문자열 검사를 한다.

 

s='abaaba'
first=0
last=5
while first < last : # 종단조건 
    if s[first] == s[last]: # 앞의 값과 뒤의 값이 같아야만 회문 부분문자열에 성립
        first+=1 
        last-=1 # first,last 한 칸씩 앞으로,뒤로 옮긴다.
    else: # 같지 않으면 회문 부분문자열이 아니므로 더이상 검사하지 않는다.
        break
if first>=last: # 회문부분문자열이 맞다면 break에 걸리지 않고 종단조건에 걸린다.
    ret = s[0:5] # 'abaaba'는 회문 부분문자열이 맞으므로 저장해준다.

해당 while문을 끝까지 돈다면, 회문 부분문자열이 되고 first>= last 조건이 성립하게된다. 이를 저장해준다.

 

그 후 두 번째로 큰 문자열을 검사해야하지만, 가장 큰 회문 부분문자열이 될 수 있는 문자열에서 값이 나왔으므로,

아래는 더 검사할 필요가 없겠다.

 

위의 코드들을 합쳐서 만든 코드는 아래와 같다.

 

문제풀이)

 

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret=""
        if len(s)==1: #주어진 string이 하나면 그대로 반환
            return s
        elif len(s)==2: # string이 두개면 바로 비교 후 반환
            if s[0]==s[1]:
                return s
            else:
                return s[0]
        else:
            for i in range(len(s)):
                if len(ret) >len(s[i:]): 
                    # 이미 저장한 회문부분문자열의 길이가 새로 비교할 전체 문자열보다 길다면 검사할 필요 없음
                    break
                if s[i] in s[i+1:]:
                    res_list = [idx for idx, value in enumerate(s[i+1:]) if value == s[i]]
                    res_list.reverse()
                    for d in res_list:
                        first=i
                        last=d+i+1
                        if len(ret) > len(s[first:last+1]):
                            # 구한 회문부분문자열 길이가 더 크면 검사할 필요 없음
                            break
                        while first < last : # 회문 부분문자열 검사 코드
                            if s[first] == s[last]:
                                first+=1
                                last-=1
                            else:
                                break
                        if first>=last:
                            if len(s[i:d+i+1+1]) > len(ret): # 이번에 구한 회문 부분문자열 값이 기존 값보다 크면 변경
                                ret=s[i:d+i+1+1]
                else:
                    continue
        if ret=="": # 회문 부분 문자열이 없을 경우 첫번째 값 반환
            return s[0]
        return ret

 

해당 결과는 성공했지만, 성능이 좋진 않았다.

실행시간이 너무 긴 것을 보면, 좀 더 줄일 수 있는 방법을 고려해야 할 것 같다.

 

실행시간이 짧은 코드를 보니 for 한번으로 돌려버린 저런 멋진 코드.. 최고다..

 

string == string[::-1] # 회문 부분문자열을 검사하는 코드.. 나의 python 무지함이 드러나는 킬포..

class Solution:
    
    def longestPalindrome(self, string: str) -> str:
        if len(string) <= 1 or string == string[::-1]:
            return string

        start = 0
        length = 1

        for i in range(len(string)):
            odd = string[i - length - 1 : i + 1]
            even = string[i - length : i + 1]

            if 0 <= i - length - 1 and odd == odd[::-1]:
                start = i - length - 1
                length += 2
            elif 0 <= i - length and even == even[::-1]:
                start = i - length
                length += 1

        return string[start : start + length]