Python程式：查詢包含特定字串的最小子字串

假設我們有兩個字串 s 和 t。我們需要在 s 中找到最小的子字串，其中 t 也是該子字串的子序列。如果不存在這種型別的子字串，我們將返回一個空字串，如果有多個最小的子字串，我們將取最左邊的那個。

因此，如果輸入類似於 s = "abcbfbghfb"，t = "fg"，則輸出將是 fbg

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

  • N := S 的大小

  • dp := 一個新列表，大小為 N，初始化為無窮大

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

    • 如果 S[i] 與 T[0] 相同，則

      • dp[i] := 1

  • 對於 j 從 1 到 T 的大小 - 1，執行以下操作：

    • last := 一個新的對映

    • dp2 := 一個新列表，大小為 N，初始化為無窮大

    • 對於 i 從 0 到 N，執行以下操作：

      • 如果 S[i] 與 T[j] 相同，則

        • prev_i := 從 last 中返回 T[j - 1] 的值

        • 如果 prev_i 不為空，則

          • dp2[i] := dp[prev_i] + (i - prev_i)

        • last[S[i]] := i

      • dp := dp2

  • m := dp 的最小值

  • i := 返回 dp 中包含 m 的索引

  • 如果 m 為無窮大，則

    • 返回空字串

  • 返回 S[從索引 i - dp[i] + 1 到 i]

讓我們檢視以下實現以更好地理解：

示例

 即時演示

class Solution:
   def solve(self, S, T):
      INF = float("inf")
      N = len(S)
      dp = [INF] * N
      for i in range(N):
         if S[i] == T[0]:
            dp[i] = 1
      for j in range(1, len(T)):
         last = {}
         dp2 = [INF] * N
         for i in range(N):
            if S[i] == T[j]:
               prev_i = last.get(T[j − 1], None)
               if prev_i is not None:
                  dp2[i] = dp[prev_i] + (i − prev_i)
            last[S[i]] = i
         dp = dp2
      m = min(dp)
      i = dp.index(m)
      if m == INF:
         return ""
      return S[i − dp[i] + 1 : i + 1]
ob = Solution()
print(ob.solve("abcbfbghfb","fg"))

輸入

"abcbfbghfb","fg"

輸出

fbg

更新於: 2020-12-26

1K+ 瀏覽量

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告