647. Palindromic Substrings

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

Palindromic Substrings - LeetCode

 

 

DP 문제

 

string안에 얼마나 팔린드롬이 있는지 계산하는 문제이다.

 

"aaa"가 입력값이면

"a", "a", "a", "aa", "aa", "aaa"이므로 6을 리턴해야한다.

 

윈도우 사이즈로 이동하면서 하나씩 체크하면 되는데 dp_arr가 필요하다.

윈도우 1일 경우에는 모든 캐릭터가 팔린드롬이다. 

윈도우 2일 경우에는 나 자신과 바로 앞의 캐릭터가 같으면 팔린드롬이다.

 

윈도우가 3일 때 부터는

윈도우가 1인 경우와 2인 경우를 활용해서 중복계산을 안해도 되게끔 해야한다.

 

나 자신과 윈도우 사이즈만큼 떨어진 캐릭터가 같은지를 확인하고 그 이전 계산값을 활용한다.

 

aabbaa 일 경우 윈도우가 4이면

첫번째 a와 네번째 b가 같지 않으므로 False

두번째 a와 다섯번째 a가 같고 

그 사이가 팔린드롬(bb)이므로 False이다.

 

(bb는 이미 이전 윈도우 2일때 계산을 해두었다.)

 

 

 

 

class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """

        
        
        count = 0
        
        # dp_arr
        dp_arr  = [ [False for i in range(len(s))] for j in range(len(s)) ]
        
                    
        for i in range(0, len(dp_arr), 1):
            
            for j in range(0, len(dp_arr[0]), 1):
        
                if i == 0:
                    dp_arr[0][j] = True
                    count += 1
                if i == 1:
                    if j+1 < len(s):
                        if s[j] == s[j+1]:
                            dp_arr[1][j] = True
                            count += 1
                    
                if i > 1:
                    if i+j < len(s):
                        if s[j] == s[i+j] and dp_arr[i-2][j+1]:
                            dp_arr[i][j] = True
                            count +=1
                        
        #for d in dp_arr:
        #    print(d)          
        return count