使用 Python 檢查字串是否可以在 K 步內轉換的程式

假設我們有兩個字串 s 和 t，我們需要檢查 s 是否可以在 k 步或更少的步數內轉換為 t。在第 i 步，您可以執行以下操作。

  • 在 s 中選擇任何索引 j（從 1 開始），使得 1 <= j <= s 的大小，並且 j 在任何先前的移動中都沒有被選擇，並將該索引處的字元移動 i 次。

  • 保持不變。

這裡移動字元意味著用字母表中的下一個字母替換它（如果字母是 'z'，則將其環繞到 'a'）。因此，將字元移動 i 次表示應用 i 次移動操作。

因此，如果輸入類似於 s = "poput" t = "vwput" k = 9，則輸出將為 True，因為在 i = 6 時，我們可以將 'p' 轉換為 'v'，在 i = 8 時，我們可以將 'o' 轉換為 'w'。

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

  • 如果 s 的大小與 t 的大小不同，則

    • 返回 False

  • count := 一個數組，包含所有從 0 到 25 的 i 的 (1 和 (k - i + 1 +(k - i)/26) 的最小值)

  • 對於 s 中的每個字元 c1 和 t 中的每個字元 c2，執行

    • 如果 c1 與 c2 不相同，則

      • diff :=(c2 的 ASCII 碼 - c1 的 ASCII 碼 + 26) 模 26

      • 如果 count[diff] <= 0，則

        • 返回 False

      • count[diff] := count[diff] - 1

  • 返回 True

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

示例

 即時演示

def solve(s, t, k):
   if len(s) != len(t):
      return False
   count = [min(1, k - i + 1) + (k - i)//26 for i in range(26)]
   for c1, c2 in zip(s, t):
      if (c1 != c2):
         diff = (ord(c2) - ord(c1) + 26) % 26
         if count[diff] <= 0:
            return False
         count[diff] -= 1
   return True
s = "poput"
t = "vwput"
k = 9
print(solve(s, t,k))

輸入

"poput","vwput",9

輸出

True

更新於: 2021年5月29日

152 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告