python에서 최대 k개의 문자를 삭제한 후 회문을 형성할 수 있는지 확인하는 프로그램

문자열 s가 있다고 가정하고 최대 k개의 문자를 삭제한 후 이 문자열을 회문으로 만들 수 있는지 여부를 확인해야 합니다.

따라서 입력이 s ="lieuvrel", k =4와 같으면 출력은 True가 되고 3개의 문자를 삭제하여 회문 "레벨"을 얻을 수 있습니다.

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

• lcs() 함수를 정의합니다. , b
• m :=크기, n :=b 크기
• table :=크기(m + 1) x (n + 1)의 행렬이고 0으로 채움
• 1~m 범위의 i에 대해 다음을 수행합니다.
  • 1~n 범위의 j에 대해 다음을 수행합니다.
    • a[i - 1]이 b[j - 1]과 같으면
      • 테이블[i, j] :=1 + 테이블[i - 1, j - 1]
    • 그렇지 않으면
      • table[i, j] :=table[i, j - 1] 및 table[i - 1, j]의 최대값
• 반환 테이블[m, n]
• 기본 방법에서 다음을 수행합니다.
• (s의 크기 - lcs(s, s의 역) <=k)인 경우 true를 반환하고 그렇지 않으면 false를 반환

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

예시

class Solution:
   def solve(self, s, k):
      def lcs(a, b):
         m, n = len(a), len(b)
         table = [[0] * (n + 1) for _ in range(m + 1)]
         for i in range(1, m + 1):
            for j in range(1, n + 1):
               if a[i - 1] == b[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
               else:
                  table[i][j] = max(table[i][j - 1], table[i - 1][j])
         return table[m][n]

      return len(s) - lcs(s, s[::-1]) <= k
     
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

입력

"lieuvrel", 4

출력

True