[LeetCode] PalindromicSubstrings - Java

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

Palindromic Substrings - LeetCode

---

문제설명

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

 

Example 1:

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

Example 2:

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

Note:

1. The input string length won't exceed 1000.

입력문자열로 만들 수 있는 회문인 부분문자열을 모두 구하는 문제.

 

 

문제 접근
각각의 인덱스에서 만들 수 있는 회문인 부분문자열을 구하면 된다.
이 때 각각의 문자열을 중앙값으로 하여 좌우로 한칸씩 늘려가며 회문을 찾으면
불필요한 탐색을 줄일 수 있다.

 

 

소스코드

/**
 *  @문제해결
 *  각각의 인덱스를 중앙값으로 해서 양 옆으로 문자열을 늘려가며 만들 수 있는 팰린드롬을 카운팅했습니다.
 *
 *
 *  @성능
 *  Runtime: 2 ms
 *  Memory Usage: 39.1 MB
 *  시간복잡도: O(n^2) -> 최악의 경우 = 모든 문자가 같을때 (0.5n*(4+(0.5n-1)*2))/2 = O(n^2)
 *
 */
 
 
class Solution647 {
    public int countSubstrings(String s) {
        char[] str = s.toCharArray();
        int palindromCnt = 0;
 
        for(int i = 0; i < str.length; i++){
            palindromCnt += countPalindrom(i, i, str);
            palindromCnt += countPalindrom(i, i + 1, str);
        }
 
        return palindromCnt;
    }
 
    private int countPalindrom(int left, int right, char[] str){
        if(left < 0 || str.length <= right)
            return 0;
 
        if(str[left] == str[right])
            return countPalindrom(left -1, right + 1, str) + 1;
 
        return 0;
    }
}