[리트코드][JAVA] 5. longest-palindromic-substring(가장 긴 팰린드롬 부분 문자열)

💡 문제
longest-palindromic-substring (https://leetcode.com/problems/longest-palindromic-substring/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

1. 팰린드롬(Palindrome):
   • 정의: 앞으로 읽으나 뒤로 읽으나 동일한 문자열을 의미합니다.
   • 팰린드롬 판별 방법: 주어진 문자열이 팰린드롬인지 확인하기 위해 다양한 방법이 사용될 수 있습니다. 예를 들어, 문자열의 앞뒤를 비교하거나, 문자열을 뒤집어서 원본과 비교하는 방법 등이 있습니다.
2. 중심 확장법(Center Expansion):
   • 개념: 팰린드롬을 찾기 위해 문자열의 각 위치를 중심으로 확장해나가는 방법입니다.
   • 홀수 길이와 짝수 길이 팰린드롬: 중심이 하나인 경우(홀수 길이 팰린드롬)와 중심이 두 개인 경우(짝수 길이 팰린드롬)를 모두 고려하여 팰린드롬을 찾습니다.
3. 문자열 탐색 알고리즘:
   • 문자열의 각 위치 탐색: 주어진 문자열에서 특정 위치를 시작으로 팰린드롬을 탐색하는 방법이 중요합니다.
   • 효율적인 탐색: 브루트 포스보다 효율적인 방법으로 탐색하기 위해 중복 계산을 최소화하는 방법이 필요합니다. 예를 들어, 동적 계획법(Dynamic Programming)이나 Manacher's 알고리즘을 사용할 수 있습니다.

---

🤓 문제 풀이

🔨 문제 설명

변역:

문자열 s가 주어질 때, s에서 가장 긴 팰린드롬 부분 문자열을 반환하시오.

예제 1:

입력: s = "babad"

출력: "bab"

설명: "aba"도 유효한 답입니다.

예제 2:

입력: s = "cbbd"

출력: "bb"

제약 조건:

• 1 <= s.length <= 1000
• s는 오직 숫자와 영문자로만 구성됩니다.

가장 긴 팰린드롬 부분 문자열을 찾기 위해서는 주어진 문자열에서 각 위치를 중심으로 좌우로 확장해가며 팰린드롬 여부를 확인하는 방법을 사용할 수 있습니다. 팰린드롬 문자열의 길이가 짝수일 경우와 홀수일 경우를 모두 고려해야 합니다.

---

🔨 접근 방법

"주어진 문자열에서 각 위치를 중심으로 좌우로 확장해가며 팰린드롬 여부를 확인하는 방법을 사용할 수 있습니다."

이 문장은 중심 확장 기법(expand around center)을 사용하여 문제를 해결할 수 있다는 힌트를 제공합니다. 이 기법은 문자열의 각 문자를 중심으로 팰린드롬 여부를 확인하고, 중심을 기준으로 좌우로 확장하면서 가장 긴 팰린드롬 부분 문자열을 찾는 방법입니다.

---

🔨 문제 풀이 과정

• 중심 확장법:
  • 문자열의 각 문자를 중심으로 확장하여 가장 긴 팰린드롬을 찾습니다.
  • 두 개의 포인터를 사용하여 팰린드롬을 확장하는데, 중심이 하나인 경우 (홀수 길이 팰린드롬)와 중심이 두 개인 경우 (짝수 길이 팰린드롬) 모두를 고려합니다.
• 확장 함수:
  • 주어진 중심을 기준으로 좌우로 확장하여 가장 긴 팰린드롬 부분 문자열을 찾습니다.
• 전체 문자열 탐색:
  • 각 위치를 중심으로 확장하여 가장 긴 팰린드롬 부분 문자열을 갱신합니다.

---

🔨 알고리즘 선택 이유

중심 확장 알고리즘(Expand Around Center Algorithm)을 사용합니다. 이 알고리즘은 문자열의 각 문자(또는 문자 사이의 위치)를 중심으로 팰린드롬을 확장하여 가장 긴 팰린드롬 부분 문자열을 찾는 방법입니다.

1. 중심 설정:
   • 문자열의 각 문자와 각 문자의 사이(즉, 문자들 사이의 공간)을 팰린드롬의 중심으로 설정합니다. 이렇게 하면 총 2n-1개의 중심을 고려하게 됩니다. 예를 들어, 문자열 abc의 경우 'a', 'b', 'c'와 각 문자 사이의 빈 공간을 중심으로 삼아야 합니다.
2. 팰린드롬 확장:
   • 각 중심에서 좌우로 문자를 비교하며 확장합니다.
   • 두 개의 인덱스를 사용하여 팰린드롬을 확장하는데, 왼쪽 인덱스는 중심에서 왼쪽으로, 오른쪽 인덱스는 중심에서 오른쪽으로 이동합니다.
   • 문자가 동일하면 팰린드롬 확장을 계속하고, 문자가 다르면 확장을 멈춥니다.
3. 최장 팰린드롬 갱신:
   • 각 중심에서 확장한 팰린드롬의 길이를 계산하고, 현재 저장된 가장 긴 팰린드롬 길이와 비교하여 더 길면 갱신합니다.

---

🔨 구현코드

class Solution {
    public String longestPalindrome(String s) {
        // 입력 문자열이 null이거나 길이가 0이면 빈 문자열 반환
        if (s == null || s.length() < 1) return "";
        
        // 가장 긴 팰린드롬 부분 문자열의 시작과 끝 인덱스를 추적하는 변수
        int start = 0, end = 0;
        
        // 문자열의 각 문자와 각 문자 사이를 중심으로 설정하여 팰린드롬 확장
        for (int i = 0; i < s.length(); i++) {
            // 중심이 하나인 경우 (홀수 길이 팰린드롬)
            int len1 = expandAroundCenter(s, i, i);
            // 중심이 두 개인 경우 (짝수 길이 팰린드롬)
            int len2 = expandAroundCenter(s, i, i + 1);
            // 두 경우 중 더 긴 팰린드롬 길이를 선택
            int len = Math.max(len1, len2);
            // 현재까지 찾은 가장 긴 팰린드롬보다 길면 시작과 끝 인덱스를 갱신
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        // 가장 긴 팰린드롬 부분 문자열을 반환
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        // 주어진 중심을 기준으로 좌우로 확장하며 팰린드롬을 찾는 함수
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;  // 왼쪽으로 확장
            right++; // 오른쪽으로 확장
        }
        // 확장이 멈추면 팰린드롬의 길이를 반환
        // right와 left가 확장이 끝난 후 한 칸 더 이동했으므로 -1을 해줌
        return right - left - 1;
    }
}

---

📚 풀이 보완

코드 설명

• longestPalindrome 메서드:
  • start와 end 변수를 사용하여 가장 긴 팰린드롬 부분 문자열의 시작과 끝 인덱스를 추적합니다.
  • 문자열의 각 문자를 중심으로 expandAroundCenter 메서드를 호출하여 가장 긴 팰린드롬의 길이를 계산합니다.
  • 계산된 길이가 현재 저장된 가장 긴 팰린드롬보다 길면 start와 end를 갱신합니다.
• expandAroundCenter 메서드:
  • 주어진 중심을 기준으로 좌우로 확장하며 팰린드롬 문자열을 찾습니다.
  • 좌우 문자가 같을 때까지 확장하며, 확장이 멈추면 팰린드롬의 길이를 반환합니다.

---

📍 Plus+

시간 복잡도와 공간 복잡도 분석

 

시간 복잡도

공간 복잡도

요약

• 시간복잡도:
• 공간복잡도:

 

---

풀이 참고 로직