[Leetcode] 647번 - palindromic substring

문제 링크: https://leetcode.com/problems/palindromic-substrings/

1. 문제 파악

• 문제를 나눠서 정의: 주어진 문자열의 substring 중에서 좌우 대칭되는 개수 구하기
  1. 주어진 문자열에서 좌우 대칭되는 substring 찾기
  2. 좌우 대칭되는 substring을 카운트 하기
• 시간잡도 파악: 1 <= s.length <= 1000 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상

 

2. 핵심 문제 풀이 도출

문제를 나눈것에 대해 풀이를 도출해본다.

1. 좌우 대칭되는 문자열의 중앙값부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)
2. 모든 substring중에서 좌우 대칭되는 것을 카운팅해야되기 때문에, 모든 문자를 중앙값으로 두고 좌우 대칭이 되는 모든 substring을 탐색해야한다. -> O(N)

위의 핵심 알고리즘은 2번 로직이 실행될때마다 1번을 로직을 실행하므로 시간복잡도는 O(N) x O(N) = O(N^2)에 풀수있다.

 

3. 입출력 케이스 도출

• 일반 케이스
  • abc -> 3 (a, b, c)
  • aaa -> 6 (a, a, a, aa, aa, aaa)
• 엣지 케이스
  • aba -> 5 (a, b, a, ab, ba, aba)
  • aaaaa -> 15 (a, a, a, a, a, aa, aa, aa, aa, aaa, aaa, aaa, aaaa, aaaa, aaaaa)

4. 핵심 문제 풀이가 케이스에 알맞게 입출력 될수 있는지 대략적으로 확인

주어진 문자열의 모든 문자를 중앙값으로 두고 좌우 대칭 문자열을 탐색하면, 모든 좌우 대칭 substring을 찾아낼수있다.

 

중앙값을 기준으로 탐색 왼쪽 포인터와 오른쪽 포인터를 두고, 왼쪽 포인터는 1씩 감소하고 오른쪽 포인터는 1씩 추가하면서 문자 일치/불일치를 확인해서 대칭 문자열을 판별할수 있다. 포인터가 이동할때마다 substring palindromic을 찾을수있다.

 

abb에서 bb 같이 palindrome이 짝수일때는 탐색 왼쪽 포인터를 중앙 인덱스로 두고 탐색 오른쪽 포인터를 중앙 인덱스 + 1로 둔다. abbb에서 bbb와 같이 palindrome이 홀수일때는 탐색 왼쪽 포인터와 탐색 오른쪽 포인터를 동일하게 중앙 인덱스로 둔다.

 

따라서 palindrome을 찾기 전까지는 palindrome이 홀수인지 짝수인지 모르기 때문에, substring을 탐색할때, 홀수일 경우와 짝수일 경우의 수를 모두 탐색해야한다.

 

5. 어떤 자료구조와 알고리즘을 사용할지?

자료구조는 기존의 문자 배열인 문자열을 그대로 사용해서 탐색하면 되고, 알고리즘은 사실상 핵심 문제 풀이와 같다.

 

6. 코드로 문제 풀이 구현

중앙값을 기준으로 두고 양쪽 포인터를 1씩 증감시키면서 이동하며 palindromic을 찾으면 여러개 발견될수 있다. 그때마다 palindromic을 카운팅해주면된다.

class Solution {
    int count = 0;    

    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        for (int i = 0; i < s.length(); i++) { 
            countPalindrome(s, i, i); // palindrome odd length;
            countPalindrome(s, i, i + 1); // palindrome even length
        }
        return count;
    }

    private void countPalindrome(String s, int left, int right) {
        // 중앙값을 두고 palindromic을 찾으면 여러개 발견될수 있다.
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            count++;
            left--;
            right++;
        }
    }
}