資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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+ 瀏覽量
廣告