소문자 문자열 s와 다른 값 k가 있다고 가정합니다. 이제 반복되는 연속 문자를 개수와 문자로 넣어 문자열에 대해 실행 길이 인코딩을 수행하는 작업을 고려하십시오. 따라서 문자열이 "aaabbc"와 같으면 "3a2bc"로 인코딩됩니다. 여기서 "c"는 연속적으로 한 번만 나타나므로 "1c"를 넣지 않습니다. 따라서 먼저 s에서 k 연속 문자를 제거한 다음 결과 실행 길이 인코딩의 가능한 최소 길이를 찾을 수 있습니다.
따라서 입력이 s ="xxxxxyyxxxxxzzxxx", k =2와 같으면 출력은 6이 됩니다. 두 가지 분명한 선택은 "yy" 또는 "zz"를 제거하는 것입니다. "yy"를 제거하면 길이가 7인 "10x2z3x"가 생성됩니다. "zz"를 제거하면 길이가 6인 "5x2y8x"가 생성되며 이것이 가장 작습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
calc_cost() 함수를 정의합니다. 시간이 걸립니다
-
l이 0과 같으면
-
0 반환
-
-
l이 1과 같으면
-
1 반환
-
-
그렇지 않으면
-
str(l) + 1의 반환 크기
-
-
함수 접두사()를 정의합니다. 시간이 걸립니다
-
pre :=처음에는 [0, 0] 쌍이 있는 목록
-
마지막 :=null
-
s의 각 c에 대해
-
c가 마지막과 같으면
-
pre
에 쌍(pre의 마지막 항목의 0번째 요소, 1 + pre의 마지막 항목의 1번째 요소)을 삽입합니다.
-
-
그렇지 않으면
-
insert (pre의 마지막 항목의 0번째 요소) + calc_cost(pre의 마지막 항목의 첫 번째 요소, 1) into pre
-
-
마지막 :=c
-
-
사전 반환
-
-
기본 방법에서 다음을 수행합니다.
-
pre :=접두어
-
suf :=접두사의 역순(역순)
-
ans :=무한대
-
범위 0에서 s - k + 1 사이의 i에 대해 수행
-
j :=i + k
-
쌍 (왼쪽, 중간) :=pre[i]
-
쌍(오른쪽, 중간) :=suf[j]
-
비용 :=왼쪽 + 오른쪽
-
c1 :=s[i - 1] if i> 0 그렇지 않으면 null
-
c2 :=s[j] if j
-
c1이 c2와 같으면
-
비용 :=비용 + calc_cost(midl + midr)
-
-
그렇지 않으면
-
비용 :=비용 + calc_cost(midl) + calc_cost(midr)
-
-
ans :=ans 및 비용의 최소값
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
def calc_cost(l):
if l == 0:
return 0
if l == 1:
return 1
else:
return len(str(l)) + 1
class Solution:
def solve(self, s, k):
def prefix(s):
pre = [[0, 0]]
last = None
for c in s:
if c == last:
pre.append([pre[-1][0], pre[-1][1] + 1])
else:
pre.append([pre[-1][0] + calc_cost(pre[-1][1]),1])
last = c
return pre
pre = prefix(s)
suf = prefix(s[::-1])[::-1]
ans = float("inf")
for i in range(len(s) - k + 1):
j = i + k
left, midl = pre[i]
right, midr = suf[j]
cost = left + right
c1 = s[i - 1] if i > 0 else None
c2 = s[j] if j < len(s) else None
if c1 == c2:
cost += calc_cost(midl + midr)
else:
cost += calc_cost(midl) + calc_cost(midr)
ans = min(ans, cost)
return ans
ob = Solution()
s = "xxxxxyyxxxxxzzxxx"
print(ob.solve(s, 2)) 입력
s = "xxxxxyyxxxxxzzxxx"
출력
6