Leetcode - 647. Palindromic Substrings

문제

주어진 문자열에서 모든 palindrome(회문)의 substring 갯수를 구하라. substring은 연속된 부분 문자열을 의미.

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".

https://leetcode.com/problems/palindromic-substrings/

해결

중앙에서부터 시작해서 palindrome문자인지 판별하는 방법. 이 방법은 문자열이 짝수개, 홀수가 두가지 경우 모두 체크해야한다.

• "abba"
• "aba"

class Solution {
    int ssize;
    
    int palin_center(string &s, int lo, int hi) {
        int cnt = 0;
        
        while (lo >= 0 && hi < ssize) {
            if (s[lo] != s[hi])
                break;
            lo--;
            hi++;
            cnt++;
        }
        return cnt;
    }
public:
    int countSubstrings(string s) {
        ssize = s.length();
        int pcnt = 0;
        
        for (int i = 0; i < ssize; i++) {
            pcnt += palin_center(s, i, i);
            pcnt += palin_center(s, i, i + 1);
        }
        return pcnt;
    }
};