检查是否可以在Python中的给定约束下从A形成字符串B

Z时代
2024-01-10
分类：综合

假设我们有两个字符串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。

示例

让我们看下面的实现以更好地理解-

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))