Python程式：查詢可以移除的子序列長度，使得t仍然是s的子序列

Python 伺服器端程式設計程式設計

假設我們有兩個字串s和t，並且t是s的子序列。我們需要找到可以從s中移除的最大長度的子字串，使得t仍然是s的子序列。

例如，如果輸入為s = "xyzxyxz" t = "yz"，則輸出為4，因為我們可以移除子字串"abca"

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

left := 新列表，right := 另一個新列表
c1 := -1, c2 := -1, c3 := -1
j := 0
對於i從0到s的長度，執行以下操作：
- 如果s[i]與t[j]相同，則
  - 將i插入到left的末尾
  - j := j + 1
- 如果j與t的長度相同，則
  - c1 := s的長度 - i - 1
  - 退出迴圈
j := t的長度 - 1
對於i從s的長度 - 1到0，遞減1，執行以下操作：
- 如果s[i]與t[j]相同，則
  - 將i插入到right的第0個位置
  - j := j - 1
- 如果j與-1相同，則
  - c2 := i
  - 退出迴圈
對於i從0到t的長度 - 1，執行以下操作：
- c3 := c3和(right[i + 1] - left[i] - 1)中的最大值
返回c1、c2和c3中的最大值

示例（Python）

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

線上演示

class Solution:
   def solve(self, s, t):
      left = []
      right = []
      c1 = -1
      c2 = -1
      c3 = -1
      j = 0
      for i in range(len(s)):
         if s[i] == t[j]:
            left.append(i)
            j += 1
         if j == len(t):
            c1 = len(s) - i - 1
            break
      j = len(t) - 1
      for i in range(len(s) - 1, -1, -1):
         if s[i] == t[j]:
            right.insert(0, i)
            j -= 1
         if j == -1:
            c2 = i
            break
      for i in range(len(t) - 1):
         c3 = max(c3, right[i + 1] - left[i] - 1)
      return max(c1, c2, c3)
ob = Solution()
s = "xyzxyxz"
t = "yz"
print(ob.solve(s, t))

輸入

"xyzxyxz", "yz"

輸出

Arnab Chakraborty

更新於： 2020-12-22

164 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習