在 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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告