Pythonで不可逆ランレングスエンコーディングの最小長を見つけるプログラム

小文字の文字列sと別の値kがあるとします。ここで、繰り返される連続する文字をカウントおよび文字として配置することにより、文字列に対してランレングスエンコーディングを実行する操作について考えてみます。したがって、文字列が「aaabbc」のような場合、「3a2bc」としてエンコードされます。ここでは、「c」の代わりに「1c」を付けません。これは、連続して1回しか表示されないためです。したがって、最初にs内のk連続文字を削除してから、結果のrun-lengthencodingの可能な最小の長さを見つけることができます。

したがって、入力がs ="xxxxxyyxxxxxzzxxx"、k =2の場合、2つの明白な選択肢は「yy」または「zz」を削除することであるため、出力は6になります。 「yy」を削除すると、長さが7の「10x2z3x」になります。「zz」を削除すると、長さが6の「5x2y8x」になります。これが最小です。

これを解決するには、次の手順に従います-

• 関数calc_cost（）を定義します。これにはl

  かかります

• lが0と同じ場合、

  • 0を返す

• lが1と同じ場合、

  • 1を返す

• それ以外の場合

  • str（l）+1の戻りサイズ

• 関数prefix（）を定義します。これには時間がかかります

  • pre：=最初はペア[0、0]

    のリスト

  • 最後：=null

  • sの各cについて、実行します

    • cが最後と同じ場合、

      • ペア（preの最後のアイテムの0番目の要素、preの最後のアイテムの1 + 1番目の要素）をpreに挿入します

    • それ以外の場合

      • preに（preの最後の項目の0番目の要素）+ calc_cost（preの最後の項目の1番目の要素、1）を挿入します

    • 最後：=c

  • 前に戻る

• メインの方法から、次の手順を実行します。

• pre：=プレフィックス

• suf：=プレフィックスの逆順）

• ans：=無限大

• 0からsのサイズまでの範囲のiの場合-k+1、do

  • j：=i + k

  • ペア（左、中央）：=pre [i]

  • ペア（右、midr）：=suf [j]

  • コスト：=左+右

  • c1：=s [i --1] i> 0の場合、それ以外の場合はnull

  • c2：=s [j] ifj

  • c1がc2と同じ場合、

    • コスト：=コスト+ calc_cost（midl + midr）

  • それ以外の場合

    • コスト：=コスト+ calc_cost（midl）+ calc_cost（midr）

  • ans：=最小の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