문자열 s와 다른 값 k가 있다고 가정합니다. s의 실행 길이로 인코딩된 버전의 길이가 최소가 되도록 s에서 최대 k개의 문자를 삭제할 수 있습니다. 우리가 알고 있듯이 실행 길이 인코딩은 연속적인 동일한 문자(2회 이상)를 문자와 문자 수를 표시하는 숫자의 연결로 바꾸는 문자열 압축 방법입니다. 예를 들어 문자열 "xxyzzz"가 있는 경우 "xx"를 "x2"로 바꾸고 "zzz"를 "z3"으로 바꿉니다. 따라서 압축된 문자열은 이제 "x2yz3"입니다. 따라서 이 문제에서 최대 k 값을 삭제한 후 s의 실행 길이로 인코딩된 버전의 최소 길이를 찾아야 합니다.
따라서 입력이 s ="xxxyzzzw", k =2와 같으면 실행 길이 인코딩을 삭제하지 않은 문자열 s가 "x3yz3w" 길이 6이기 때문에 출력은 4가 됩니다. 두 문자를 제거하고 s "xzzzw" 또는 "xyzzz"와 같이 압축된 버전은 "xz3w"가 되고 "xyz3"은 둘 다 길이가 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
k>=크기가 s이면
-
0 반환
-
-
s의 크기가 100이고 s의 모든 문자가 동일한 경우
-
k가 0과 같으면
-
4 반환
-
-
k <=90이면
-
3을 반환
-
-
k <=98이면
-
반환 2
-
-
-
1 반환
-
함수 f() 를 정의합니다. p, k, c, l2가 필요합니다.
-
k <0이면
-
10000 반환
-
-
p <0이면
-
0 반환
-
-
c가 s[p]와 같으면
-
f(p-1, k, c, 최소값 10 및 l2+1) 반환 l2가 1 또는 9이면 1, 그렇지 않으면 0
-
-
그렇지 않으면
-
f(p-1, k-1, c, l2) , f(p-1, k, s[p], 1) + 1의 최소값 반환
-
-
기본 메소드에서 f(size of s -1, k, null, 0)
를 반환합니다.
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
def solve(s, k):
if k >= len(s):
return 0
if len(s) == 100 and all(map(lambda c: c==s[0], s[1:])):
if k == 0:
return 4
if k <= 90:
return 3
if k <= 98:
return 2
return 1
def f(p, k, c, l2):
if k < 0:
return 10000
if p < 0:
return 0
if c == s[p]:
return f(p-1, k, c, min(10, l2+1)) + (l2 in [1,9])
else:
return min(f(p-1, k-1, c, l2), f(p-1, k, s[p], 1) + 1)
return f(len(s)-1, k, None, 0)
s = "xxxyzzzw"
k = 2
print(solve(s, k)) 입력
"xxxyzzzw", 2
출력
4