Pythonで指定された制約の下でAから文字列Bを形成できるかどうかを確認します

2つの文字列sとt、および2つの値pとqがあるとします。 sがp以下の文字を持ち、各グループから最大q個の文字を選択できる最後のグループを除いて、sがp個の文字のグループに分割されるようにsからtを取得できるかどうかを確認する必要があります。また、tの文字の順序はsと同じである必要があります。

したがって、入力がs ="mnonnopeqrst"、t ="moprst"、p =5、q =2の場合、 "mnonn"、 "opeqr"、 "st"のように分割できるため、出力はTrueになります。 、「mnonn」と「opeqr」から2文字の部分文字列「mo」と「pr」を取得すると、「st」がすでに存在するため、これら2つの長さの部分文字列を使用して、単純な連結でtを生成できます。

これを解決するには、次の手順に従います-

• temp：=すべてのキーの空のリストを含む空のマップ
• l：=sの長さと同じサイズのリストで、0を入力します
• 0からsのサイズの範囲のiについては、
  • tempの最後にiを挿入['a']
• 低：=0
• 範囲0からt-1のサイズのiの場合、do
  • 指標：=temp ['a']
  • it：=インデックスは、ソートされた順序を維持するためにインデックスリストの下位に挿入します
  • インデックスのサイズ-1と同じ場合、
    • Falseを返す
  • count：=（indices [it] / p）の商
  • l [count]：=l [count] + 1
  • l [count]> =qの場合、
    • count：=count + 1
    • 低：=カウント* p
  • それ以外の場合、
    • 低：=インデックス[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