在 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

更新于: 2021年1月18日

75 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告