[LeetCode] 647. Palindromic Substrings

 

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

LeetCode - The World's Leading Online Programming Learning Platform

LeetCode - Palindromic Substrings

문제 유형 : 문자열 처리, 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

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.

 

문자열 s가 주어집니다. 팰린드롬인 부분 문자열의 개수를 구하시오.

문자열을 뒤집어도 같으면 팰린드롬이라고 합니다.

 

풀이

1. O(n^3)의 풀이

인덱스 0부터 순차적으로 탐색하면서, 뒤 인덱스의 글자를 하나씩 붙인다.

매번 문자열이 팰린드롬인지 확인하면서 개수를 추가한다.

 

2. O(n^2)의 풀이

인덱스 0부터 순차적으로 탐색하는데, 그 인덱스를 중심으로 하여 좌우에 각각 문자를 붙여보면서 팰린드롬을 만든다.

홀짝의 경우를 위해서 I를 중심으로 하거나, I, I+1을 중심으로 두는 케이스를 더한다.

더 팰린드롬에 본질적인 풀이이다.

 

코드

C++ - O(n^3)풀이

class Solution {
public:
    bool isPalindrome(string &str) {
        for(int i = 0; i < str.size()/2; i++) {
            if(str[i] != str[str.size()-i-1]) return false;
        }
        return true;
    }

    int countSubstrings(string s) {
        const int n = s.size();

        int cnt = 0;

        for(int i = 0; i < n; i++) {
            string str = "";

            for(int j = i; j < n; j++) {
                str += s[j];
                if(isPalindrome(str)) cnt++;
            }
        }

        return cnt;
        
    }
};

 

GO - O(n^2)풀이

func getPalindrome(left, right int, str string) int {
    cnt := 0
    for left >= 0 && right < len(str) && str[left] == str[right] {
        cnt++
        left--
        right++
    }
    return cnt
}

func countSubstrings(s string) int {
    n := len(s)
    cnt := 0
    for i := 0; i < n; i++ {
        cnt += getPalindrome(i, i, s)
        cnt += getPalindrome(i, i+1, s)
    }
    return cnt
}