파이썬에서 단어 및 문자 수 목록에서 생성할 수 있는 최대 문자열 수를 계산하는 프로그램

<시간/>

각 문자열에 두 개의 문자 "A"와 "B"가 포함된 문자열 목록이 있다고 가정합니다. 우리는 두 개의 값과 b를 가지고 있습니다. 우리는 형성할 수 있는 최대 문자열 수를 찾아야 합니다. 재사용 없이 최대 "A" 개수와 최대 b개 "B"를 사용할 수 있습니다.

따라서 입력이 문자열 =["AAABB", "AABB", "AA", "BB"] a =4 b =2인 경우 출력은 2가 됩니다. 4 "A "와 2개의 "B"["AABB","AA"].

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

쌍:=새 목록
문자열의 각 w에 대해 다음을 수행합니다.
- A :=w의 "A" 수
- B :=w의 크기 - A
- 쌍의 끝에 쌍(A, B) 삽입
ans :=(a, b) 값이 0인 지도
각 pait(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 :=임시
as의 모든 값 목록의 최대값을 반환합니다.

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

예시

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