資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢包含給定子字串的最小字串大小
假設我們有兩個字串 s 和 t，我們需要找到 s 中包含 t 中所有字元的最小子字串的大小。如果不存在這樣的子字串，則返回 -1。
因此，如果輸入類似於 s = "thegrumpywizardmakes" t = "wake"，則輸出將為 10，因為包含 "wake" 的最短子字串是 "wizardmake"（長度為 10）。
為了解決這個問題，我們將遵循以下步驟：
counter := b 中每個字元的頻率
start := 0
min_subs := 無窮大
rem := b 中不同字元的數量
對於 end 從 0 到 a 的大小，執行以下操作：
current := a[end]
如果 current 在 counter 中，則：
counter[current] := counter[current] - 1
如果 counter[current] 等於 0，則：
rem := rem - 1
當 rem 等於 0 時，執行以下操作：
prev_char := a[start]
如果 prev_char 在 counter 中，則：
counter[prev_char] := counter[prev_char] + 1
如果 counter[prev_char] > 0，則：
rem := rem + 1
min_subs := min_subs 和 (end - start + 1) 的最小值
start := start + 1
當 min_subs 不為無窮大時返回 min_subs，否則返回 -1
示例（Python）
讓我們看看以下實現以更好地理解：
class Solution:
def solve(self, a, b):
counter = {}
for char in b:
counter[char] = counter.get(char, 0) + 1
start = 0
min_subs = float("inf")
rem = len(counter)
for end in range(len(a)):
current = a[end]
if current in counter:
counter[current] -= 1
if counter[current] == 0:
rem -= 1
while rem == 0:
prev_char = a[start]
if prev_char in counter:
counter[prev_char] += 1
if counter[prev_char] > 0:
rem += 1
min_subs = min(min_subs, end - start + 1)
start += 1
return min_subs if min_subs != float("inf") else -1
ob = Solution()
s = "thegrumpywizardmakes"
t = "wake"
print(ob.solve(s, t))輸入
"thegrumpywizardmakes", "wake"
輸出
2
更新於: 2020-12-21
346 次瀏覽
廣告