檢查Python中是否可以使用給定約束條件從另一個字串形成一個字串

假設我們有兩個小寫字串s和t。我們必須檢查是否可以使用以下約束條件從s生成t：

  • t的字元存在於s中，例如，如果t中有兩個'a'，則s中也應該有兩個'a'。

  • 當t中的任何字元不在s中時，檢查s中是否存在前兩個字元（前兩個ASCII值）。例如，如果'f'在t中但不在s中，則可以使用s中的'd'和'e'來構成'f'。

因此，如果輸入類似於s = "pghn" t = "pin"，則輸出將為True，因為我們可以使用'g'和'h'來構成'i'從而構成"pin"。

為了解決這個問題，我們將遵循以下步驟：

  • freq := s中每個字元的頻率
  • 對於範圍0到t的大小，執行以下操作：
    • 如果freq[t[i]]不為零，則
      • freq[t[i]] := freq[t[i]] - 1
    • 否則，如果freq[t[i]的前一個字元]和freq[t[i]的前兩個字元]不為零，則
      • 將freq[t[i]的前一個字元]減少1
      • 將freq[t[i]的前兩個字元]減少1
    • 否則，
      • 返回False
  • 返回True

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

from collections import defaultdict
def solve(s, t):
   freq = defaultdict(lambda:0)
   for i in range(0, len(s)):
      freq[s[i]] += 1
   for i in range(0, len(t)):
      if freq[t[i]]:
         freq[t[i]] -= 1
      elif (freq[chr(ord(t[i]) - 1)] and freq[chr(ord(t[i]) - 2)]):
         freq[chr(ord(t[i]) - 1)] -= 1
         freq[chr(ord(t[i]) - 2)] -= 1
      else:
         return False
   return True
s = "pghn"
t = "pin"
print(solve(s, t))

輸入

"pghn", "pin"

輸出

True

更新於：2020-12-29

260 次檢視

開啟你的職業生涯

完成課程後獲得認證

開始
廣告