Pythonの単語と文字数のリストから生成できる文字列の最大数をカウントするプログラム

各文字列に2文字の「A」と「B」が含まれている文字列のリストがあるとします。 aとbの2つの値があります。形成できるストリングの最大数を見つける必要があります。再利用せずに、最大で最大b個の「A」と最大b個の「B」を使用できます。

したがって、入力がstrings =["AAABB"、 "AABB"、 "AA"、 "BB"] a =4 b =2の場合、4 "Aを使用して文字列を取得できるため、出力は2になります。 "sと2つの"B"s ["AABB "、"AA"]。

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

• ペア：=新しいリスト
• 文字列の各wについて、
  • A：=wの「A」の数
  • B：=wのサイズ-A
  • ペアの最後にペア（A、B）を挿入します
• ans：=（a、b）の値が0のマップ
• ペアの各ペイト（A、B）について、
  • temp：=ansからの新しいマップ
  • 各ペア（temp_a、temp_b）、およびansの値wcについて、実行します
    • temp_a>=Aおよびtemp_b>=Bの場合、
      • rem：=a pait（temp_a-A、temp_b-B）
      • temp [rem]：=temp [rem]の最大値（remがない場合は0）および（wc + 1）
    • ans：=temp
• ansのすべての値のリストの最大値を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, strings, a, b):
      pairs = []
      for w in strings:
         A = w.count("A")
         B = len(w) - A
         pairs.append((A, B))
      ans = {(a, b): 0}
      for A, B in pairs:
         temp = dict(ans)
         for (temp_a, temp_b), wc in ans.items():
            if temp_a >= A and temp_b >= B:
               rem = (temp_a - A, temp_b - B)
               temp[rem] = max(temp.get(rem, 0), wc + 1)
         ans = temp
      return max(ans.values())

ob = Solution()
strings = ["AAABB", "AABB", "AA", "BB"]
a = 4
b = 2
print(ob.solve(strings, a, b))

入力

["AAABB", "AABB", "AA", "BB"], 4, 2

出力

2