Leet code (Medium): 5. Longest Palindromic Substring (중심확장법)- Java

 

이것 또한 투포인터를 사용해야하는 문제이다.

다만 최대 길이의 palindrome 문자열을 찾아야한다.

 

난두가지 방법을 생각했다.

1. 첫번째 문자부터 마지막 문자를 가리키는 포인터를 앞당기며 찾음. (가장자리 -> 가운데 방향으로 palindrome 탐색)
2. 문자 하나씩을 기준으로 삼고 양쪽으로 확장하며 찾음. (가운데 -> 가장자리 방향으로 palindrome 탐색)

1번은 시간복잡도 O(n^3), 2번은 시간복잡도 O(n^2)이다.

따라서, 2번의 중심확장방식이 더 효율적이다.

 

팰린드롬(palindrome) 문제는 '좌우대칭'이라는 팰린드롬의 특성에 따라, 

시간복잡도를 줄이기 위해 최대길이 문제는 가운데 기준점을 찍으며 찾아가는 2번 방식이 효율적이다.

 

1번 방식)

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <= 1){
            return s;
        }

        int maxLen = 1;
        String maxStr = s.substring(0,1);

        int start = 0;
        while(s.substring(start, s.length()).length() > maxLen){
            for(int end = s.length(); end > start; end--){
                String str = s.substring(start, end);
                int len = str.length();
                if(len > maxLen && isPalindrome(str)){
                    maxLen = len;
                    maxStr = str;
                }
            }
            start++;
        }
        
        
        return maxStr;

    }

    private boolean isPalindrome(String subs){
        int start = 0; 
        int end = subs.length() - 1;

        while(start <= end){
            char currStart = subs.charAt(start);
            char currEnd = subs.charAt(end);
            if(currStart != currEnd){
                return false;
            }
            start++;
            end--;
        }

        return true;
    }
}

 

 

2번 방식)

class Solution {
    public String longestPalindrome(String s) {
        if(s.length() <=1){
            return s;
        }
        
        // 최대 길이 팰린드롬 문자열의
        // 시작, 끝을 가리킬 포인터
        int maxStart = 0;
        int maxEnd = 0;

        for(int i = 0; i < s.length(); i++){
            // 홀수길이 팰린드롬 (가운데가 문자)
            int len1 = expandFromCenter(s, i, i);
            // 짝수길이 팰린드롬 (가운데가 문자 사이)
            int len2 = expandFromCenter(s, i, i+1);

            // 둘중 더 긴 길이로 세팅
            int len = Math.max(len1, len2);

            if(len > maxEnd - maxStart){
                // 홀수일경우, 짝수일경우를 고려해서 세팅해야함.
                maxStart = i - (len-1)/2;
                maxEnd = i + len/2;
            }
            
        }

        return s.substring(maxStart, maxEnd + 1);
    }

    private int expandFromCenter(String s, int left, int right){
        while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }

        // 팰린드롬이 아닐때 while 문에서 나오므로 -1 해줘야함.
        return right - left - 1;
    }
}