数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序：计算从单词列表和字母计数中可以生成的最大字符串数量
假设我们有一个字符串列表，其中每个字符串包含两个字母“A”和“B”。我们有两个值a和b。我们必须找到可以形成的最大字符串数量。我们可以最多使用a个“A”和最多b个“B”，无需重复使用。
因此，如果输入类似于strings = ["AAABB", "AABB", "AA", "BB"] a = 4 b = 2，则输出将为2，因为我们可以使用4个“A”和2个“B”形成字符串 ["AABB","AA"]。
为了解决这个问题，我们将遵循以下步骤：
- pairs := 一个新的列表
- 对于strings中的每个w，执行以下操作：
- A := w中“A”的数量
- B := w的大小 - A
- 在pairs的末尾插入一个(A, B)对
- ans := 一个映射，其中(a, b)的值为0
- 对于pairs中的每个(A, B)对，执行以下操作：
- temp := 从ans复制的一个新的映射
- 对于ans中的每个(temp_a, temp_b)对和值wc，执行以下操作：
- 如果temp_a >= A 且 temp_b >= B，则执行以下操作：
- rem := 一个(temp_a - A, temp_b - B)对
- temp[rem] := temp[rem]（如果rem不存在，则为0）和(wc + 1)中的最大值
- ans := temp
- 如果temp_a >= A 且 temp_b >= B，则执行以下操作：
- 返回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
更新于: 2020年12月2日
232 次查看
广告