[DP] Palindromic Substrings

Palindrome은 거꾸로 읽어도 똑같은 string이라고 한다.

예시를 보면 원소 한개는 palindrome이라고 생각하고, 그 외에 palindrome한 조합의 갯수를 찾는것으로 보인다.

 

전형적인 DP문제이다.

s가 n개라고 할때, 0부터 n까지의 모든 케이스에 대해 palindrome이 있는지 찾으면 된다.

이 과정에서 시작위치를 left, 끝위치를 right로 두었다.

 

 

다섯글자로 구성된 s가 input으로 들어온다고 가정해보자.

for문에서 검사하는 조합은 ( i , i )와 ( i , i+1) 이다.

따라서 검정색 동그라미로 표기된 조합은 Palindrome여부에 대한 검사가 가능하다.

 

그림에서 x로 표기된 조합은 검사할 필요가 없다. 

시작위치가 끝위치보다 크기 때문이다.

 

문제는 for문에서 직접 검사하지 않는 붉은색 동그라미로 표기된 조합들이다.

이는 for문에서 검사하는 조합에 Loop를 이용해 검사할 수 있다.

예컨데 (0,3)에 해당하는 부분이 Palindrome인지 여부를 알고싶다고 해보자

 

for문에서는 (1,2)조합에 대해서는 이미 검사를 한다.

만약 1,2가 Palindrome이라면, 0,3은 s[0]과 s[3]만 같아도 Palindrome이라고 할 수 있다.

따라서 left와 right를 각각 조정해주면 원하는 검사가 가능하다.

이러한 방식으로 붉은색 동그라미 케이스를 모두 검사할 수 있다.

만약 (1,2) 조합이 Palindrome이 아니라면 (0,3)은 Palindrome일수없기때문에 추가적인 검사가 필요하지 않다.