[LeetCode] 5. Longest Palindromic Substring [Java/Python3]

문제

5. Longest Palindromic Substring

Longest Palindromic Substring - LeetCode

회문 문제의 일종으로 주어진 문자열 중에서 회문인 가장 긴 문자열을 뽑아내는 문제이다.

접근방식

처음 이 문제를 접했을 때는 너무나 자연스럽게 이중포문으로 전부 순회하고자 했으나, 역시 시간복잡도 측면에서 개선의 여지가 있을 것 같아 조금 더 깊이 생각을 해보았다. 하지만 결국 구글링의 도움을 받아 조금 더 적합한 방향을 잡을 수 있었는데, 해당 방법은 특정 인덱스에서 그 이전 문자열의 길이를 탐색해 나아가면서 정답을 업데이트 해 나아가는 것이다.

찾아본 답안을 조금 더 쉽게 개선하여 답안에 작성했다. 여기서 주의해야할 점은 문자열을 순회하는 지점에서 특정 인덱스 이전의 문자열을 탐색하는데, 길이가 0일 때, 1 내지는 2개 차이가 나는 이전 시점의 문자열을 고려해야 한다는 점이다. "aba"라는 문자열에서 0번째 문자와 1번째 문자의 조합은 "a", "b", "ab" 정도로 길이가 1로 업데이트되고, 그 이후에 2번째 문자열에서 길이가 2인 것을 찾게 된다면 "ba"만 고려하기 때문이다. 즉 글자수에 따라 "a" -> "aba" 같은 케이스를 고려해야하므로 2개 이전의 문자열들을 확인해야만 한다.

만약 조금 더 개선의 여지가 있다면 현재 접근 방식은 회문인 문자열을 찾기위해 하나씩 늘려가면서 찾아가는 방식인데, 긴 문자열만 우선적으로 찾으면 되는 문제인 만큼, 주어진 전체 문자열에서 하나씩 줄여가면서 긴 문자열을 먼저 찾는 방식을 도입하면 조금 더 줄일 수 있지 않을까 싶다.

답안

Java / 70 ms / 54.5 MB

class Solution {
    public String longestPalindrome(String s) {
        
        int start = 0;
        int length = 0;
        
        for(int i=0; i<s.length(); i++){
            if(isPalindrome(s.substring(i-length, i+1))){
                start = i-length;
                length = length+1;
            } else if(i-length-1>=0 && isPalindrome(s.substring(i-length-1, i+1))){
                start = i-length-1;
                length = length+2;
            }
        }
        
        return s.substring(start, start+length);
    }
    
    // Palindrome Check
    public Boolean isPalindrome(String s){
        
        for(int i=0; i<s.length()/2; i++){
            if(s.charAt(i) != s.charAt(s.length()-1-i)){
                return false;
            }
        }
        
        return true;
    }
}

Python3 / 141 ms / 13.9 MB

class Solution:
    
    def longestPalindrome(self, s: str) -> str:
        
        # 논리: 
        # Palindrome이면 갱신 후 검토하는 글자를 하나씩 늘리기 + bab 같은 예외케이스를 위해 간격을 하나더 추가해서 검토하기
        # Palindrome이 아니면 그냥 순환한다.
        
        # test 예시 : "aababbbb"
        # index, string_start_index, string_length / string
        # 0 0 0 / a
        # a
        # 1 0 1 / aa
        # aa
        # 2 0 2 / aab
        # 3 0 2 / aba
        # aba
        # 4 1 3 / abab
        # 5 1 3 / babb
        # 6 1 3 / abbb
        # 7 1 3 / bbbb
        # bbbb
        
        start, length = 0, 0
        for i in range(len(s)):
            
            # debug
            # print(i, start, length)
            # print("candidate: ", s[start:start+length])
            # print("up: ", s[i-length: i+1])
            # print("down: ", s[i-length-1: i+1])            
            
            # even            
            if isPalindrome(s[i-length: i+1]):
                start, length = i-length, length+1
            # odd
            elif (i-length-1>=0) and isPalindrome(s[i-length-1: i+1]):
                start, length = i-length-1, length+2
        
        return s[start:start+length]
    
# 회문여부
def isPalindrome(word: str) -> bool:

    # word_length = len(word)
    # for i in range(0, int(word_length/2)):
    #     if word[i] != word[word_length-i-1]:
    #         return False
    # return True

    return word == word[::-1]