पायथन में दूसरी स्ट्रिंग के सभी वर्णों को समाहित करने वाली सबसे छोटी विंडो खोजें

मान लीजिए हमारे पास दो स्ट्रिंग्स s1 और s2 हैं। हमें s1 में सबसे छोटा उपस्ट्रिंग ढूंढना है जिसमें s2 के सभी वर्ण कुशलतापूर्वक उपयोग हों।

इसलिए, यदि इनपुट s1 = "I am a student", s2 = "mdn" है, तो आउटपुट "m a studen" होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• N := 256 (ASCII वर्णों के लिए)
• str_len := len(main_str), patt_len := len(pattern)
• यदि str_len < patt_len, तो None लौटाएं।
• hash_pat := [0] * N, hash_str := [0] * N
• i को 0 से patt_len-1 तक: hash_pat[ord(pattern[i])] += 1
• start := 0, start_index := -1, min_len := infinity
• count := 0
• j को 0 से str_len-1 तक के लिए:
  • hash_str[ord(main_str[j])] += 1
  • यदि hash_pat[ord(main_str[j])] != 0 और hash_str[ord(main_str[j])] <= hash_pat[ord(main_str[j])], तो count += 1
  • यदि count == patt_len:
    • जब तक hash_str[ord(main_str[start])] > hash_pat[ord(main_str[start])] या hash_pat[ord(main_str[start])] == 0:
      • यदि 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
    • यदि 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(patt_len):
        hash_pat[ord(pattern[i])] += 1
    start, start_index, min_len = 0, -1, float('inf')
    count = 0
    for j in range(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