팰린드롬 문장

최대 13개의 서로 다른 단어가 주어질 때, 공백을 지운 문자열이 팰린드롬이 되는 단어 부분집합의 배열 개수를 구하는 문제입니다.

어려움8

동적 계획법

비트 연산

문자열

문자열 매칭

아직 제출이 없습니다

시간 제한2초

메모리 제한128 MB

지민이는 서로 다른 단어 N개를 가지고 있다. 이 단어들 중 일부를 골라 한 줄로 배열해 문장을 만들 때, 공백을 모두 제거한 문자열이 팰린드롬이면 그 문장을 팰린드롬 문장이라고 한다.

문장은 하나 이상의 단어로 이루어져야 하며, 인접한 두 단어 사이에는 공백이 하나 들어간다. 각 단어는 한 문장에서 최대 한 번 사용할 수 있다.

공백을 제거한 문자열이 같더라도 단어를 나눈 위치나 순서가 다르면 서로 다른 문장으로 센다. 예를 들어 a ba와 ab a는 서로 다른 문장이다.

만들 수 있는 팰린드롬 문장의 개수를 구하라.