[Leetcode 5] Longest Palindromic Substring - 투 포인터+슬라이딩윈도우

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

Longest Palindromic Substring - LeetCode

Problem

가장 긴 팰린드롬 부분 문자열을 출력하라.

 

Example

입력 | dcbabcdd

 

출력 | dcbabcd

 

 

전략

다이나믹 프로그래밍으로도 풀 수 있는 문제다. 그렇지만 이번엔 성능이 좋은 투포인터로 풀이를 해보려 한다. 전략은 가장 작은 형태에서 시작해서 확장하는 방식으로 진행한다. 무슨 말인지 다음 그림을 보면 이해가 간다.

 

 

크기가 2인 양끝을 비교해가며 왼쪽에서 오른쪽으로 진행한다. 이때 양끝이 같으면 확장하는 방식인데 위와 같은 그림은 dd에서 멈추고 확장을 더이상 할 수 없는 상태라 제일 긴 펠린드롬이 dd이다.

 

크기가 3인 경우에도 펠린드롬이 존재할 수 있다. 다음 그림을 보면 이해가 간다.

 

 

 

 

크기가 홀수인 3으로 양끝을 비교해가며 왼쪽에서 오른쪽으로 진행한다. 이때 양 끝이 같으면 확장한다. 위 그림은 bab에서 멈추고 계속 확장하다가 dcbabcd에서 긴 펠린드롬을 찾을 수가 있다. 

 

이렇게 짝수와 홀수인 크기의 두개의 투포인터와 슬라이딩 윈도우로 다음을 구현할 수가 있다. 

String 길이가 0이나 1인 경우는 바로 리턴하도록 예외처리를 한다.

 

public class Palindromic {
    int left, maxLen;

    public void expand(String s, int j, int k) {
        while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
            j--;
            k++;
        }
        if (maxLen < k - j - 1) {
            left = j + 1;
            maxLen = k - j - 1;
        }

    }


    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }

        for (int i = 0; i < len - 1; i++) {
            expand(s, i, i + 1);
            expand(s, i, i + 2);
        }

        return s.substring(left, left + maxLen);
    }
}

 

 

• 위 코드의 시간복잡도는 각 인덱스 i에 대해, 홀수 길이 투포인터, 짝수길이 투포인터를 호출한다.
• 문자열 길이를 n 이라 할때, 약 2n번의 expan호출이 있다.
• 각 expend 호출은 최악의 경우 문자열의 길이에 비례하는 시간이 걸린다. 즉 , 한 번의 확장이 O(n) 시간이 걸릴 수 있다.
• 따라서 전체 알고리즘의 시간복잡도는 O(n²)이 된다.