Minimum Window Substring
لديك سلسلتان نصيتان، s وt. أوجد أقصر مقطع فرعي من s، أي سلسلة من المحارف المتتالية، يحتوي على كل محرف في t، مع احتساب التكرارات: إذا احتوى t على حرف مرتين، فيجب أن يحتوي المقطع الفرعي عليه مرتين على الأقل. لا يهم الترتيب، ويمكن للمقطع الفرعي أن يحتوي على محارف أخرى أيضًا.
إذا كان هناك عدة مقاطع فرعية لها أقصر طول، فأعِد المقطع الواقع إلى اليسار. إذا لم يحتوِ أي مقطع فرعي من s على جميع محارف t، فأعِد سلسلة نصية فارغة.
الدالة
- sstring
- السلسلة النصية المراد البحث فيها
- tstring
- الأحرف التي يجب أن تحتوي عليها النافذة، مع التكرارات
- تُرجعstring
- أقصر سلسلة فرعية من s تحتوي على جميع أحرف t، وعند تساوي الطول تكون الأسبق من اليسار، أو سلسلة فارغة
القيود
1 ≤ s.length ≤ 5 × 1041 ≤ t.length ≤ 104sوtيحتويان على أحرف إنجليزية فقط. الأحرف الكبيرة والصغيرة أحرف مختلفة.- عندما تكون هناك عدة سلاسل فرعية هي الأقصر، تكون الإجابة هي الأسبق من اليسار؛ وعندما لا توجد أي سلسلة، تكون الإجابة
"".
أمثلة
- المدخلات
- s = "mappingtheplan"t = "nap"
- المخرجات
- "plan"
- الشرح
- عند القراءة من اليسار، أول نافذة تحتوي على
nوaوpهيappin، وطولها خمسة أحرف. أماplanفي النهاية فتحتوي على الأحرف الثلاثة كلها في أربعة أحرف، ولا توجد أي سلسلة من ثلاثة أحرف تفعل ذلك.
- المدخلات
- s = "banana"t = "aan"
- المخرجات
- "ana"
- الشرح
- يطلب
tنسختين منaونسخة واحدة منn. يحتويanaعند الفهرس 1 على ذلك تمامًا. يبدأanaآخر عند الفهرس 3، وتكون الأولوية للأيسر.
- المدخلات
- s = "Coddy"t = "cd"
- المخرجات
- ""
- الشرح
- الحرف C الوحيد في
Coddyهو حرف كبير، والحروف الكبيرة والصغيرة أحرف مختلفة. لا تحتوي أي سلسلة فرعية علىcصغيرة، لذا فالإجابة هي سلسلة فارغة.
+17 اختبارات مخفية عند الإرسال
سؤال إضافي
عندما تستخدم t بضعة أحرف فقط وتكون s طويلة، فإن معظم s لا يمكن أن يكون ذا صلة أبدًا. هل يمكنك جعل النافذة تقفز فقط بين المواضع التي تحتوي على حرف من t؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
النافذة التي تحتوي على كل
tتظل كذلك عند إطالتها، والنافذة التي ينقصها شيء ما تظل كذلك عند تقصيرها. استفد من ذلك لتجنب تجربة كل بداية مع كل نهاية.حرّك الحافة اليمنى إلى الأمام حتى تغطي النافذة
t. ثم حرّك الحافة اليسرى إلى الأمام ما دامت النافذة لا تزال تغطيt، وسجّلها في كل مرة. لا تحتاج أيّ من الحافتين إلى الرجوع إلى الخلف أبدًا.احتفظ بجدول يبيّن عدد النسخ الإضافية التي تحتاج إليها النافذة من كل حرف، ورقم واحد،
missing، لعدد النسخ التي ينقصها إجمالًا. لا يقلّmissingعند دخول حرف إلا إذا كانت النافذة لا تزال بحاجة إليه، ولا يزيد عند مغادرة حرف إلا إذا أصبحت النافذة بحاجة إلى نسخ إضافية منه. تحتوي النافذة علىtبالضبط عندما تكون قيمةmissingهي 0.
الحل
تعتمد الإجابة على عدد مرات ظهور كل حرف في النافذة، لا على ترتيبها، ويمكن أن تبدأ أفضل نافذة من أي موضع. تجربة كل بداية مع كل نهاية تعني وجود O(n²) نافذة. يكمن الحل في نافذة لا تتحرك حافتاها إلا إلى الأمام: توسّعها الحافة اليمنى حتى تغطي t، وتقلّصها الحافة اليسرى ما دامت تغطيه، ويخبرك عدّاد واحد للأحرف الناقصة بخطوة واحدة ما إذا كانت تغطي t.
وسّع نافذة من كل نقطة بداية
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت موضع بداية السلسلة الفرعية. ثم وسّعها حرفًا واحدًا في كل مرة، مع إحصاء عدد مرات ظهور كل حرف فيها، وبعد كل خطوة تحقّق مما إذا كانت تغطي t: لكل واحد من الأحرف المختلفة u التي يستخدمها t، يجب أن تحتوي النافذة على عدد من النسخ لا يقل عن عدد النسخ الموجودة في t. أول نهاية تحقق هذا الشرط تعطي أقصر نافذة تغطي المطلوب لهذه البداية، لأن كل نافذة أقصر تبدأ من الموضع نفسه جرى فحصها أولًا وفشلت. توقّف عندها.
كرّر ذلك لكل بداية واحتفظ بأقصر نافذة. تُجرَّب البدايات من اليسار إلى اليمين، ولا تحلّ نافذة محل الأفضل إلا إذا كانت أقصر منها تمامًا؛ لذلك، عند تساوي طول النوافذ، تبقى النافذة الواقعة في أقصى اليسار.
تكون هذه الطريقة بطيئة عندما تكون النوافذ طويلة أو لا تحتوي على الأحرف المطلوبة. فإذا كان الحرف Z الوحيد في s يقع في نهايتها تمامًا وكان t يتطلب واحدًا منه، فستقرأ كل بداية حتى النهاية: نحو n²/2 خطوة، أي 1.25 × 10^9 عندما تكون n = 5 × 10^4، مع فحص يصل إلى 52 حرفًا في كل خطوة. ويحدث الأمر نفسه عندما لا توجد أي نافذة مطابقة.
الخوارزمية
- احسب عدد مرات ظهور كل حرف تطلبه
t، وسجّل الحروف التي تستخدمها. - لكل
start، صفّر جدول العدّ، وحرّكendمنstartحتى نهايةs، مع إضافةs[end]إلى الجدول. - بعد كل إضافة، تحقّق من كل حرف في
t. إذا كانت النافذة تحتوي على عدد كافٍ من كل حرف، فقارن طولها بأفضل طول حتى الآن، واحتفظ بها إذا كانت أقصر منه تمامًا، ثم توقّف عن توسيعها. - بعد معالجة جميع قيم البداية، أعد أفضل نافذة، أو
""إذا لم تغطِّ أي نافذة أحرفt.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
best_start, best_len = 0, len(s) + 1
for start in range(len(s)):
have = [0] * 128 # counts inside s[start..end]
for end in range(start, len(s)):
have[ord(s[end])] += 1
if all(have[c] >= need[c] for c in letters):
# The first end that covers t gives the shortest window from this start.
if end - start + 1 < best_len:
best_start, best_len = start, end - start + 1
break
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]نافذة منزلقة تتحقق من كل حرف
الفكرة
هناك حقيقتان تلغيان الحاجة إلى إعادة البدء. إضافة أحرف إلى نافذة تحتوي على t تُبقيها محتوية عليه، وإزالة أحرف من نافذة ينقصها شيء ما تُبقيها تفتقده. لذا، عندما يتحرك الطرف الأيسر إلى اليمين، لا يمكن للطرف الأيمن لأقصر نافذة تحتوي على t إلا أن يبقى مكانه أو يتحرك إلى اليمين. يمكن للطرفين أن يتقدما معًا، ولا يعود أيٌّ منهما إلى الخلف أبدًا.
حرّك right عبر s، مضيفًا كل حرف إلى جدول للتكرارات. كلما احتوت النافذة على t، تصبح مرشحة: سجّلها إذا كانت أقصر من أفضل نافذة حتى الآن، ثم أزل s[left] وحرّك left إلى الأمام، ثم تحقّق مجددًا. كرّر ذلك حتى تتوقف النافذة عن احتواء t، ثم عُد إلى توسيعها من جهة اليمين.
لن تفوتنا أي نافذة. لنأخذ أفضل نافذة، من L إلى R. إذا كان left قد تجاوز L قبل أن يصل right إلى R، لكانت هناك نافذة تبدأ من L وتنتهي قبل R وتحتوي على t، ولكانت أقصر من أفضل نافذة. لذا، عندما يصل right إلى R، تحرّك حلقة تقليص النافذة left حتى L وتسجّل أفضل نافذة. يتحرك كل طرف بحد أقصى n مرة، لكن كل عملية تحقّق تقرأ ما يصل إلى u من التكرارات، واحدًا لكل حرف يستخدمه t، رغم أن تكرارًا واحدًا فقط قد تغيّر منذ آخر عملية تحقّق.
الخوارزمية
- احسب عدد مرات ظهور كل حرف في
tوسجّل حروفها؛ ابدأ بنافذة فارغة، وleft = 0، وبأفضل طول يساويn+1. - حرّك
rightعبر كل فهرس وأضفs[right]إلى أعداد مرات الظهور في النافذة. - ما دام كل حرف في
tيظهر في النافذة بالعدد الكافي، سجّل النافذة إذا كان طولها أقصر تمامًا من الأفضل، وأزِلs[left]من أعداد مرات الظهور وحرّكleftإلى الأمام. - أعِد أفضل نافذة، أو
""إذا ظل أفضل طول يساويn+1.
def minWindow(s, t):
need = [0] * 128 # copies of each character code that t asks for
for ch in t:
need[ord(ch)] += 1
letters = [c for c in range(128) if need[c] > 0]
have = [0] * 128 # counts inside s[left..right]
def covers():
for c in letters:
if have[c] < need[c]:
return False
return True
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
have[ord(s[right])] += 1 # expand on the right
while covers(): # shrink from the left while the window still covers t
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
have[ord(s[left])] -= 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]النافذة المنزلقة مع عدّاد للعناصر المفقودة
الفكرة
احتفظ بالنافذة نفسها واستبدل عملية التحقق برقم واحد. لتكن need[c] عدد نسخ c التي يطلبها t مطروحًا منها عدد النسخ داخل النافذة. تعني القيمة الموجبة أن النافذة ما زالت تفتقد بعض النسخ، وتعني القيمة السالبة أنها تحتوي على نسخ زائدة. لتكن missing إجمالي عدد النسخ التي تفتقدها النافذة، وتبدأ بطول t. تغطي النافذة t تمامًا عندما تكون missing تساوي 0.
يستغرق تحديثها خطوة واحدة. عندما يدخل s[right] وكانت قيمة need له أكبر من 0، فإنه يسد فجوة، لذا تنخفض missing بمقدار واحد؛ وفي كل الأحوال تنخفض need بمقدار واحد، وقد تصبح أقل من 0 لتمثل نسخة زائدة. عندما يغادر s[left]، ترتفع need بمقدار واحد، وإذا أصبحت الآن أكبر من 0، فهذا يعني أن النافذة أخرجت نسخة يحتاج إليها t، لذا ترتفع missing بمقدار واحد. تأتي النسخ الزائدة وتذهب دون أن تؤثر في missing.
تتبّع s = banana وt = aan: تبدأ need بقيمة 2 للحرف a و1 للحرف n، وتبدأ missing بقيمة 3. الحرف b غير مطلوب. يجعل الحرف a الأول missing تساوي 2، ويجعلها الحرف n تساوي 1، ثم يجعلها الحرف a الثاني تساوي 0، لذا تغطي bana الحروف المطلوبة في t. يؤدي تقليص النافذة إلى إسقاط الحرف b الزائد والإبقاء على ana، المكوّنة من ثلاثة أحرف، وهي الأفضل حتى الآن. يؤدي إسقاط ذلك الحرف a إلى إعادة missing إلى 1. تغطي النافذة مرة أخرى عند الحرف a الأخير، مع nana، التي تُقلَّص إلى ana الثانية. طولها ليس أقل، لذا تبقى ana الأولى من جهة اليسار.
يدخل كل حرف من s النافذة مرة واحدة ويغادرها مرة واحدة كحد أقصى، وتستغرق كل حركة مقدارًا ثابتًا من العمل. يقرأ إنشاء need السلسلة t مرة واحدة. يستغرق التنفيذ بأكمله O(n + m)، ويكون جدول من 128 قيمة للعدّ هو الذاكرة الإضافية الوحيدة.
الخوارزمية
- املأ
needبأعداد مرات ظهورt، واضبطmissingعلى طولt، وleft = 0، وأفضل طول علىn+1. - لكل
right: إذا كانت قيمةneed[s[right]]أكبر من 0، فقلّلmissing؛ ثم قلّلneed[s[right]]. - ما دام
missingيساوي 0، سجّل النافذة إذا كان طولها أقصر من الأفضل بصورة صارمة. ثم زِدneed[s[left]]؛ وإذا أصبحت الآن أكبر من 0، فزِدmissing. حرّكleftإلى الأمام. - أعِد أفضل نافذة، أو
""إذا ظل أفضل طول يساويn+1.
def minWindow(s, t):
# need[c]: copies of c that t asks for minus copies inside the window.
# Positive means the window still lacks c; negative means it holds spares.
need = [0] * 128
for ch in t:
need[ord(ch)] += 1
missing = len(t) # characters of t the window does not cover yet
left = 0
best_start, best_len = 0, len(s) + 1
for right in range(len(s)):
c = ord(s[right])
if need[c] > 0: # this copy fills a gap
missing -= 1
need[c] -= 1
while missing == 0: # the window covers t: record it, then shrink
if right - left + 1 < best_len:
best_start, best_len = left, right - left + 1
c = ord(s[left])
need[c] += 1
if need[c] > 0: # gave away a copy t needs
missing += 1
left += 1
if best_len > len(s):
return ""
return s[best_start:best_start + best_len]
أخطاء شائعة وحالات حدّية
غالبًا ما تُحصي الإجابات الخاطئة الشيء غير الصحيح أو تسجّل النافذة في اللحظة غير المناسبة.
- عدّ الحروف بدلًا من النسخ. يتطلب
t = aanوجود حرفَيa، لذا لا يغطيهban. - إنقاص
missingلكل محرف يدخل. حرفaثالث زائد؛ فإذا أنقصmissing، يصل العداد إلى 0 بينما لا تزال النافذة تفتقر إلىn. أنقصه فقط عندما تكونneedأكبر من 0. - زيادة
missingلكل محرف يغادر. إزالة محرف زائد تُبقي النافذة مغطيةً لـt؛ زِده فقط عندما تصبحneedأكبر من 0. - تسجيل النافذة بعد حلقة التقليص. عندها لن تعود تغطي
t. سجّلها داخل الحلقة، قبل إزالةs[left]. - استبدال أفضل نافذة عندما تكون النافذة الجديدة مساوية لها في الطول. سيؤدي ذلك إلى إرجاع النافذة الأقصر الواقعة إلى أقصى اليمين؛ استخدم مقارنة أصغر من الصارمة.
- استخدام
nطولًا لقيمة «غير موجود». عندما تكون الإجابة هيsبأكملها، يكون طولهاnأيضًا. ابدأ منn+1كي تختلف الحالتان. - استخدام جدول من 26 خانة مفهرسًا بـ
c - 'a'. تقع الأحرف الكبيرة خارج نطاقه. استخدم خانة واحدة لكل رمز محرف.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة أقصر سلسلة فرعية تحتوي على جميع المحارف المطلوبة؟
تعمل النافذة المنزلقة مع عدّاد النواقص في زمن O(n + m)، حيث إن n وm هما طولا s وt. يؤدي إنشاء الجدول إلى قراءة t مرة واحدة، ويدخل كل حرف من s النافذة ويخرج منها مرة واحدة على الأكثر، بتكلفة ثابتة لكل حركة. الذاكرة الإضافية هي جدول يحتوي على عدد واحد لكل رمز حرفي، ولا يزداد حجمه مع حجم المدخلات.
لماذا لا تتحرك الحافة اليسرى إلى الخلف أبدًا؟
لا تتجاوز الحافة اليسرى موضعًا إلا بعد أن تكون نافذة تبدأ منه قد غطّت t، وكانت تلك أقصر نافذة تغطية تبدأ من ذلك الموضع. وكل نافذة تبدأ هناك وتنتهي لاحقًا تكون أطول، لذا فإن الرجوع إلى الوراء لن يؤدي أبدًا إلى العثور على إجابة أفضل. ولهذا تتحرك الحافتان إلى الأمام مرة واحدة، ويبقى العمل خطيًا.
ما الذي يعدّه العداد المفقود؟
هو عدد نسخ الأحرف التي يطلبها t ولا تحتوي عليها النافذة بعد، أي مجموع القيم الموجبة في need. يبدأ بطول t، ويصبح 0 بالضبط عندما تغطي النافذة t. النسخ الزائدة لا تغيّره أبدًا، وهذا ما يتيح لمقارنة واحدة أن تحل محل فحص كل حرف.
ما الفرق بين مسألة السلسلة الفرعية ذات النافذة الدنيا وبين العثور على ترتيبٍ مختلف للأحرف في سلسلة نصية؟
يتكوّن الجناس الناقص من الأحرف نفسها الموجودة في t دون أي أحرف أخرى، لذا يكون طول النافذة ثابتًا ويساوي m، وتتحرك خطوة واحدة في كل مرة. هنا، قد تحتوي النافذة على أحرف إضافية، لذا يُعد طولها جزءًا من الإجابة: فهي تنمو من اليمين حتى تشمل t، ثم تنكمش من اليسار ما دامت لا تزال تشملها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def minWindow(s, t):
# اكتب الشيفرة هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "mappingtheplan" t = "nap"
المتوقع
"plan"