LeetCode - Palindromic Substrings

문제 설명

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

입출력 예시

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

제약사항

1 <= s.length <= 1000
s consists of lowercase English letters.

Solution

[전략]

• 배열을 순회하며 i번째를 중심으로 palindromic인지 확인함. 짝수, 홀수인 경우 나눠서 카운트

import java.util.*;

class Solution {
     public int countSubstrings(String s) {

        int paldromCount = s.length(); // 문자가 단독으로 사용된 경우 count
        for (int i = 0; i < s.length(); i++) {

            paldromCount = paldromCount + checkPalindrome(s, i, i + 1) + checkPalindrome(s, i - 1, i + 1); // substring이 짝수개, 홀수개인 경우 나눠서 계산
        }
        return paldromCount;
    }
    
    private int checkPalindrome(String s, int leftIdx, int rightIdx) {
        int count = 0;
        while (leftIdx >= 0 && rightIdx < s.length() && s.charAt(leftIdx) == s.charAt(rightIdx)) {
            count++;
            leftIdx--;
            rightIdx++;
        }
        return count;
    }
}