[Leetcode] 647. Palindromic Substrings

Identifying the Problem

string 문자열에서 가능한 모든 palindromic substrings의 개수를 구한다.

Organizing thoughts

전체적인 아이디어는 5번 문제와 유사하고, dp가 true인 경우의 개수를 센다고 보면 된다.

하나의 차이점을 두자면, 이번 문제는 window slicing으로 window의 개수를 늘려가며 탐색하였다.

 

[Leetcode] 5. Longest Palindromic Substring

Sourcecode

class Solution {
public:
    int countSubstrings(string s) 
    {
        int m = s.size();
        vector<vector<int>> dp(m , vector(m,0));
        int ans = 0;
        
        for(int i = 0; i<m; i++)
        {
            dp[i][i] = 1;
            ans++;
        }
        
        for(int w = 1; w<m; w++)
        {
            for(int k = 0; k<m-w; k++)
            {
                if( ( (dp[k+1][w+k-1] == 1 || w==1  )&& s[k] == s[w+k]) ) 
                //window의 size가 1 이거나, 이전 값이 true 인 경우
                //양 끝이 동일한 문자면 해당 substring은 Palindromic 이다.
                {    
                  dp[k][w+k] = 1;
                  ans++;
                }
            }
        }

        return ans;
    } 
    
    
};