7294 : 재귀 팰린드롬 분할
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
문자열 $S$를 부분 문자열들이 모두 팰린드롬이 되도록 분할하는 모든 경우를 출력하십시오.
백트래킹으로 구현합니다: 현재 위치에서 시작하여 팰린드롬인 부분 문자열을 선택하고 재귀 호출합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
백트래킹으로 구현합니다: 현재 위치에서 시작하여 팰린드롬인 부분 문자열을 선택하고 재귀 호출합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 영문 소문자로 이루어진 문자열 $S$가 주어집니다. (길이 $\le 12$)
출력 설명
$S$를 팰린드롬으로만 분할하는 모든 경우를 줄바꿈으로 출력합니다.
각 분할은 구분자
각 분할은 구분자
|로 표시합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
aab
출력 예시
COPY
복사되었습니다!
복사되었습니다!
a|a|b
aa|b도움
def backtrack(start, path): if start==len(s): result.append('|'.join(path)); return; for end in range(start+1, len(s)+1): if is_palindrome(s[start:end]): path.append(s[start:end]); backtrack(end, path); path.pop()