Leetcode - Palindromic Substrings[Java]

문제 출처: https://leetcode.com/problems/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".

Constraints:

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

문제 풀이

class Solution {
    
    static int count;
    
    public int countSubstrings(String s) {
        int start = 0; 
        int end = 0;
        count = 0;
        for(int i = 0; i < s.length(); i++) {
            findAll(s, i, i);
            findAll(s, i, i + 1);
        }
        return count;
    }
    
    public static void findAll(String s, int left, int right) {
        
        while(true) {
            if(left < 0 || right > s.length() - 1) {
                return;
            } else {
                if(s.charAt(left) == s.charAt(right)) {
                    count++;
                } else {
                    return;
                }
            }
            left--;
            right++;
        }
    }
}

가능한 팰린드롬의 총 개수를 구하는 문제이다.

집합은 아니고, 문자열의 인덱스 별로 찾는 문제여서 팰린드롬이 가능한 총 중앙값의 수 2n - 1를 스캔하는 방식으로 접근 했다.

중앙값의 수 스캔 방법 참고 링크 <--- 클릭