在 Python 中检查是否可以在给定约束条件下从字符串 A 形成字符串 B
假设我们有两个字符串 s 和 t,以及两个值 p 和 q。我们必须检查是否可以从 s 获取 t,使得 s 被分成 p 个字符一组,除了最后一组最多包含 p 个字符,并且我们可以从每一组中最多选择 q 个字符,并且 t 中字符的顺序必须与 s 相同。
所以,如果输入类似于 s = "mnonnopeqrst",t = "moprst",p = 5,q = 2,则输出将为 True,因为我们可以进行如下划分:"mnonn"、"opeqr"、"st"。现在,通过从 "mnonn" 和 "opeqr" 中分别取 2 个字符的子字符串 "mo" 和 "pr",然后 "st" 已经存在,因此使用这两个长度的子字符串,我们可以通过简单的连接生成 t。
为了解决这个问题,我们将遵循以下步骤:
- temp := 一个空映射,其中所有键都包含空列表
- l := 一个大小与 s 长度相同的列表,并用 0 填充
- 对于 i 从 0 到 s 的大小,执行以下操作:
- 将 i 插入到 temp['a'] 的末尾
- low := 0
- 对于 i 从 0 到 t 的大小 - 1,执行以下操作:
- indices := temp['a']
- it := 在 indices 列表中插入 low 的索引,以保持排序顺序
- 如果 it 等于 indices 的大小 - 1,则:
- 返回 False
- count := (indices[it] / p) 的商
- l[count] := l[count] + 1
- 如果 l[count] >= q,则:
- count := count + 1
- low := count * p
- 否则:
- low := indices[it] + 1
- 返回 True
示例
让我们看一下以下实现,以便更好地理解:
from bisect import bisect_left from collections import defaultdict def solve(s, t, b, m) : temp = defaultdict(list) l = [0] * len(s) for i in range(len(s)) : temp['a'].append(i) low = 0 for i in range(len(t)) : indices = temp['a'] it = bisect_left(indices, low) if it == len(indices) : return False count = indices[it] // b l[count] = l[count] + 1 if l[count] >= m : count += 1 low = count * b else : low = indices[it] + 1 return True s = "mnonnopeqrst" t = "moprst" p = 5 q = 2 print (solve(s, t, p, q))
输入
"mnonnopeqrst", "moprst", 5, 2
输出
True
广告