Pythonで別の文字列のすべての文字を含む文字列内の最小のウィンドウを検索します

2つの文字列s1とs2があるとすると、s2のすべての文字が効率的に使用されるように、s1で最小の部分文字列を見つける必要があります。

したがって、入力がs1 ="I am a student"、s2 ="mdn"の場合、出力は "mastuden"になります

これを解決するには、次の手順に従います-

• N：=26

• str_len：=main_strのサイズ、patt_len：=パターンのサイズ

• str_len

  • なしを返す

• hash_pat：=サイズNの配列で、0で埋める

• hash_str：=サイズNの配列で、0で埋める

• 0からpatt_lenの範囲のiの場合、実行

  • hash_pat [ASCII of（pattern [i]）]：=hash_pat [ASCII of（pattern [i]）] + 1

• start：=0、start_index：=-1、min_len：=inf

• カウント：=0

• 0からstr_lenの範囲のjの場合、実行

  • hash_str [ASCII of（main_str [j]）]：=hash_str [ASCII of（main_str [j]）] + 1

  • hash_pat [ASCII of（main_str [j]）]が0と同じでなく、hash_str [ASCII of（main_str [j]）] <=hash_pat [ASCII of（main_str [j]）]の場合、

    • count：=count + 1

  • countがpatt_lenと同じ場合、

    • hash_str [ASCII of（main_str [start]）]> hash_pat [ASCII of（main_str [start]）]またはhash_pat [ASCII of（main_str [start]）]は0と同じですが、実行してください

      • hash_str [ASCII of（main_str [start]）]> hash_pat [ASCII of（main_str [start]）]の場合、

        • hash_str [ASCII of（main_str [start]）]：=hash_str [ASCII of（main_str [start]）]-1

      • start：=start + 1

    • len_window：=j --start + 1

    • min_len> len_windowの場合、

      • min_len：=len_window

      • start_index：=start

• start_indexが-1と同じ場合、

  • なしを返す

• 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