在Python中查詢包含另一個字串所有字元的最小視窗

假設我們有兩個字串s1和s2，我們需要找到s1中最小的子串，使得s2的所有字元都能被有效利用。

因此，如果輸入類似於s1 = "I am a student"，s2 = "mdn"，則輸出將是"m a studen"

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

  • N := 26

  • str_len := 主字串的長度，patt_len := 模式的長度

  • 如果 str_len < patt_len，則

    • 返回 None

  • hash_pat := 一個大小為N的陣列，並填充為0

  • hash_str := 一個大小為N的陣列，並填充為0

  • 對於 i 從 0 到 patt_len，執行

    • hash_pat[pattern[i] 的ASCII碼] := hash_pat[pattern[i] 的ASCII碼] + 1

  • start := 0, start_index := -1, min_len := 無窮大

  • count := 0

  • 對於 j 從 0 到 str_len，執行

    • hash_str[main_str[j] 的ASCII碼] := hash_str[main_str[j] 的ASCII碼] + 1

    • 如果 hash_pat[main_str[j] 的ASCII碼] 不等於 0 並且 hash_str[main_str[j] 的ASCII碼] <= hash_pat[main_str[j] 的ASCII碼]，則

      • count := count + 1

    • 如果 count 等於 patt_len，則

      • 當 hash_str[main_str[start] 的ASCII碼] > hash_pat[main_str[start] 的ASCII碼] 或 hash_pat[main_str[start] 的ASCII碼] 等於 0 時，執行

        • 如果 hash_str[main_str[start] 的ASCII碼] > hash_pat[main_str[start] 的ASCII碼]，則

          • hash_str[main_str[start] 的ASCII碼] := hash_str[main_str[start] 的ASCII碼] - 1

        • start := start + 1

      • len_window := j - start + 1

      • 如果 min_len > len_window，則

        • min_len := len_window

        • start_index := start

  • 如果 start_index 等於 -1，則

    • 返回 None

  • 返回 main_str 的子串（從索引 start_index 到 start_index + min_len）

示例

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

N = 256
def get_pattern(main_str, pattern):
   str_len = len(main_str)
   patt_len = len(pattern)
   if str_len < patt_len:
      return None
   hash_pat = [0] * N
   hash_str = [0] * N
   for i in range(0, patt_len):
      hash_pat[ord(pattern[i])] += 1
   start, start_index, min_len = 0, -1, float('inf')
   count = 0
   for j in range(0, str_len):
      hash_str[ord(main_str[j])] += 1

      if (hash_pat[ord(main_str[j])] != 0 and hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])]):
         count += 1
      if count == patt_len:
         while (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] or hash_pat[ord(main_str[start])] == 0):
      if (hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])]):
         hash_str[ord(main_str[start])] -= 1
         start += 1
      len_window = j - start + 1
      if min_len > len_window:
         min_len = len_window
         start_index = start
   if start_index == -1:
      return None
   return main_str[start_index : start_index + min_len]
main_str = "I am a student"
pattern = "mdn"
print(get_pattern(main_str, pattern))

輸入

"I am a student", "mdn"

輸出

m a studen

更新於：2020年8月27日

397 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告