Python程式：透過移除首尾元素並重新插入建立目標字串

假設我們有兩個字串 S 和 T，它們互為排列。假設存在一個操作，其中我們移除 S 的第一個或最後一個字元，並將其插入字串中的任何位置。然後找到將 S 轉換為 T 所需的最少操作次數。

因此，如果輸入類似於 s = "zyvxw" t = "vwxyz"，則輸出將為 3，因為這些操作為：移除 "w" 並將其插入 "v" 後面得到 "zyvwx"，移除 "z" 並將其插入 "x" 後面得到 "yvwxz"，移除 "y" 並將其插入 "x" 後面得到 "vwxyz"。

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

  • ans := s 的大小，n := s 的大小

  • 對於 i 從 0 到 n-1，執行以下操作

    • k := 0

    • 對於 j 從 i 到 n-1，執行以下操作

      • 對於 k 從 k 到 t 的大小，執行以下操作

        • 如果 s[j] 等於 t[k]，則

          • ans := ans 和 n - (j - i + 1) 的最小值

          • 退出迴圈

      • k := k + 1

    • 返回 ans

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

示例

 線上演示

class Solution:
   def solve(self, s, t):
      ans = n = len(s)

      for i in range(n):
         k = 0
         for j in range(i, n):
            for k in range(k, len(t)):
               if s[j] == t[k]:
                  ans = min(ans, n - (j - i + 1))
                  break
            k += 1

      return ans

ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))

輸入

"zyvxw", "vwxyz"

輸出

5

更新於： 2020年10月7日

91 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告