파이썬에서 회문을 분할할 수 있는 여러 가지 방법을 찾는 프로그램

<시간/>

문자열 s가 있다고 가정하고 각 부분이 회문(palindrome)이 되도록 문자열을 분할할 수 있는 방법의 수를 찾아야 합니다.

따라서 입력이 s ="xyyx"와 같으면 ["x", "yy", "x"], ["x", "y", "와 같이 분할되므로 출력은 3이 됩니다. y", "x"], ["xyyx"].

이 문제를 해결하기 위해 다음 단계를 따릅니다.

n :=s의 크기
table :=크기가 n + 1인 목록 및 0으로 채우기
테이블[0] :=1
0에서 n 사이의 i에 대해
- 0 ~ i - 1 범위의 j에 대해 수행
  - sub :=s[인덱스 j에서 i까지]
  - sub가 회문이면
    - 테이블[i] :=테이블[i] + 테이블[j]
테이블의 마지막 요소 반환

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

예시

class Solution:
   def solve(self, s):
      n = len(s)
      table = [1] + [0] * n
      for i in range(n + 1):
         for j in range(i):
            sub = s[j:i]
            if sub == sub[::-1]:
               table[i] += table[j]
      return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

입력

"xyyx"