حلولي في كودرهب

النافذة الأمنية

صعب20 نقطةPython

الوصف

تخيّل نفسك محلّلًا في مركز الدفاع السيبراني. لديك سجلّات نصّية طويلة، وتبحث عن “بصمة تهديد” (سلسلة من الأحرف تمثّل شيفرة خبيثة). المطلوب هو إيجاد أقصر نافذة من السجل تحتوي كل أحرف البصمة مع تكراراتها.

تنبيه مهم (تعريف النافذة): المقصود بالنافذة هنا هو Substring (مقطع متّصل من السلسلة)، وليس Subsequence (تسلسل غير متّصل). أي أن الأحرف يجب أن تأتي في مقطع متواصل داخل السجل.

شرط التكرار: إذا احتوت البصمة على أحرف مكرّرة، فيجب أن تتضمن النافذة العدد المطلوب من كل حرف. مثال: إذا كانت البصمة = AABC فلابد أن تحتوي النافذة على حرف A مرّتين على الأقل، وحرف B مرّة، وحرف C مرّة.

المخرَج عند عدم التوفّر: إذا لا توجد أي نافذة صالحة تحقق الشرط، يجب إعادة سلسلة فارغة "".

مثال 1

السجل: "ADOBECODEBANC" البصمة: "ABC" أقصر نافذة تستوفي الشرط هي: "BANC".

مثال 2 (يوضح التكرار)

السجل: "AAABBC" البصمة: "AABC" أقصر نافذة تستوفي الشرط هي: "AABB"، لأنها تحتوي A مرتين، وB مرة، وC غير موجود—لذا نُكمِل إلى "AABBC" لتشمل C. الناتج النهائي: "AABBC".

مثال 3 (لا يوجد حل)

السجل: "XYZ" البصمة: "AABC" لا توجد نافذة صالحة ⇒ المخرَج: "".

أمثلة

المدخلاتالمخرجات المتوقعة
log = "ADOBECODEBANC"، pattern = "ABC""BANC"
log = "a"، pattern = "a""a"
log = "a"، pattern = "aa"""
log = "aa"، pattern = "aa""aa"

الحل

from typing import List
def minWindowSignature(log: str, pattern: str) -> str:
    from collections import Counter
    if not log or not pattern or len(pattern) > len(log):
        return ""
    need = Counter(pattern)
    missing = len(pattern)
    left = 0
    best_start, best_len = 0, len(log) + 1
    for right, ch in enumerate(log):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            need[log[left]] += 1
            if need[log[left]] > 0:
                missing += 1
            left += 1
    return "" if best_len > len(log) else log[best_start:best_start + best_len]

ملاحظات

هذه مسألة أقصر نافذة تحتوي كل الأحرف (Minimum Window Substring)، وحلها بنافذة منزلقة ومؤشرين.

  • نحفظ في need عدد ما نحتاجه من كل حرف، وفي missing عدد الأحرف الناقصة.
  • المؤشر الأيمن يوسّع النافذة حتى تكتمل الأحرف (missing == 0).
  • ثم يضيّقها المؤشر الأيسر ما دامت مكتملة، ونحفظ أقصر نافذة.

إذا لم تكتمل أي نافذة، نرجع "". التكرار محسوب: البصمة AABC تحتاج حرفي A.

التعقيد: O(n) في الوقت.

في هذه الصفحة