Python에서 문자열 회문을 만드는 데 필요한 최소 문자 수를 확인하는 프로그램

<시간/>

문자열 s가 있다고 가정하고 문자열이 회문(palindrome)이 되도록 삽입하는 데 필요한 최소 문자 수를 찾아야 합니다.

따라서 입력이 s ="mad"와 같으면 출력은 2가 됩니다. "am"을 삽입하여 "madam"을 얻을 수 있기 때문입니다.

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

함수 dp()를 정의합니다. 이것은 i, j가 걸릴 것입니다
i>=j이면
- 0 반환
s[i]가 s[j]와 같으면
- 반환 dp(i + 1, j - 1)
그렇지 않으면
- dp(i + 1, j) 및 dp(i, j - 1) + 1 중 최소값 반환
기본 방법에서 다음을 수행하십시오.
반환 dp(0, s - 1의 크기)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution:
   def solve(self, s):
      def dp(i, j):
         if i >= j:
            return 0
         if s[i] == s[j]:
            return dp(i + 1, j - 1)
         else:
            return min(dp(i + 1, j), dp(i, j - 1)) + 1
      return dp(0, len(s) - 1)
ob = Solution()
s = "mad"
print(ob.solve(s))

입력

s = "mad"