[NeetCode-LeetCode] Palindromic Substrings JAVA

반응형

728x90

[NeetCode-LeetCode] Palindromic Substrings - Medium 

---

접근

• 중심 확장

---

풀이

팰린드롬을 만족하는 부분 문자열을 찾는 문제이다. 문자열 내에 존재하는 모든 부분 문자열에 대해 팰린드롬을 검사하고 개수를 반환하여야 한다. 똑같은 문자라도 문자열 내 위치가 다르다면 한 개의 부분 문자열로 취급한다. 예시에 있는 "aaa" 문자열의 경우에도 첫 번째 두 번째 세 번째 a 모두 개별 문자로 취급하여 "aaa" 문자열의 총 부분 팰린드롬 문자열은 "a", "a", "a", "aa", "aa", "aaa"로 6개의 팰린드롬 부분 문자열을 가지고 있다. 

 

팰린드롬이란 데칼코마니처럼 문자열을 앞으로 읽어도 뒤로 읽어도 동일한 문자열을 말한다. 팰린드롬 문자열인지 검사를 하기 위한 방법은 여러 가지가 있는데 문자열의 양쪽 끝에서 중심으로 검사하는 방법이 있고 중앙에서부터 양쪽 끝으로 검사하는 방법이 있다. 이 문제에선 문자열 내 모든 부분 문자열에 대해 검사를 다 해야 하므로 중앙에서부터 양쪽 끝으로 검사해 나가는 방법을 사용한다.

    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;

        for (int center = 0; center < 2 * n - 1; center++) {
            int left = center / 2;
            int right = left + center % 2;

            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
        }

        return count;
    }

문자 단위로 접근해 접근한 문자를 중심으로 보고 팰린드롬을 검사하게 되는데 center의 범위가 원본 문자열의 길이 x 2 - 1까지로 되어 있는데 일반적으로 한 문자를 중심으로 보고 팰린드롬을 검사하는 경우엔 가운데 문자가 1개인 홀수 길이의 팰린드롬을 검사하는 경우이다. 그러나 팰린드롬은 홀수 길이만 존재하는 것이 아닌 짝수 길이의 팰린드롬도 존재하기 때문에 중심이 두 문자로 이루어진 팰린드롬과 같이 검사를 하기 위해 최대 범위가 저렇게 작성된 것이다. 

문자열 "abc"

center = 0 홀수 팰린드롬 "a"  가 중심
center = 1 짝수 팰린드롬 "ab" 가 중심
center = 2 홀수 팰린드롬 "b"  가 중심
center = 3 짝수 팰린드롬 "bc" 가 중심
center = 4 홀수 팰린드롬 "c"  가 중심

문자열의 길이는 3이지만 실제로 5번 (2 * 3 - 1) 의 연산을 수행해야 모든 경우를 검사 가능

위처럼 홀수 짝수를 모두 고려해야 결과를 얻을 수 있다. 나머지 코드는 양쪽 문자가 같은지와 정상 범위인지 체크하고 검사를 이어나가는 과정이다.

---

전체 코드

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int count = 0;

        for (int center = 0; center < 2 * n - 1; center++) {
            int left = center / 2;
            int right = left + center % 2;

            while (left >= 0 && right < n && s.charAt(left) == s.charAt(right)) {
                count++;
                left--;
                right++;
            }
        }

        return count;
    }
}