পাইথনে অন্য স্ট্রিংয়ের সমস্ত অক্ষর ধারণকারী একটি স্ট্রিংয়ের সবচেয়ে ছোট উইন্ডোটি খুঁজুন

ধরুন আমাদের দুটি স্ট্রিং s1 এবং s2 আছে, আমাদের s1-এ সবচেয়ে ছোট সাবস্ট্রিংটি খুঁজে বের করতে হবে যাতে s2-এর সমস্ত অক্ষর দক্ষতার সাথে ব্যবহার করা হবে৷

সুতরাং, যদি ইনপুট হয় s1 ="আমি একজন ছাত্র", s2 ="mdn", তাহলে আউটপুট হবে "m a studen"

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• N :=26

• str_len :=main_str এর আকার, patt_len :=প্যাটার্নের আকার

• যদি str_len

  • কোনটিই ফেরত দিন

• hash_pat :=N আকারের একটি অ্যারে এবং 0

  দিয়ে পূরণ করুন

• hash_str :=N আকারের একটি অ্যারে এবং 0

  দিয়ে পূরণ করুন

• আমি 0 থেকে patt_len এর মধ্যে, কর

  • 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

  • যদি হ্যাশ_প্যাট[ASCII of(main_str[j]) ] 0 এবং hash_str[ASCII of(main_str[j]) ] <=hash_pat[ASCII of(main_str[j]) ] এর মত না হয়, তাহলে

    • গণনা :=গণনা + 1

  • যদি গণনা patt_len এর মত হয়, তাহলে

    • যখন হ্যাশ_স্ট্র[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_index -1 এর মত হয়, তাহলে

  • কোনটিই ফেরত দিন

• main_str[index 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