Minimum Window Substring
لديك سلسلتان، s وt. أوجد أقصر سلسلة فرعية من s تحتوي على كل محارف t، مع احتساب التكرارات: إذا احتوت t على حرف مرتين، فيجب أن تحتوي السلسلة الفرعية عليه مرتين على الأقل. لا يهم الترتيب، ويمكن أن تظهر فيها محارف أخرى أيضًا.
إذا كانت هناك عدة سلاسل فرعية لها أقصر طول، فأعِد السلسلة الواقعة إلى أقصى اليسار. إذا لم تحتوِ أي سلسلة فرعية على كل محارف 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. لا يحتوي أي جزء فرعي على حرفcصغير، لذا فالإجابة هي السلسلة الفارغة.
سؤال إضافي
عندما يحتوي t على عدد قليل من الأحرف ويكون s طويلًا، فإن معظم s لا يكون مهمًا أبدًا. هل يمكنك جعل النافذة تقفز فقط بين المواضع التي تحتوي على حرف من t؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تظل النافذة التي تحتوي على
tكاملةً كذلك عند إطالتها، وتظل النافذة التي ينقصها شيء ما تفتقده عند تقصيرها. استفد من ذلك لتجنب تجربة كل بداية مع كل نهاية.حرّك الحافة اليمنى إلى الأمام حتى تغطي النافذة
t. ثم حرّك الحافة اليسرى إلى الأمام ما دامت النافذة لا تزال تغطيt، وسجّلها في كل مرة. لا تحتاج أي من الحافتين إلى الرجوع إلى الخلف.احتفظ بجدول يبيّن عدد النسخ الإضافية التي تحتاج إليها النافذة من كل حرف، وبعدد واحد،
missing، يبيّن إجمالي عدد النسخ التي تنقصها. لا يقلّل الحرف الذي يدخل قيمةmissingإلا إذا كان لا يزال مطلوبًا، ولا يزيدها الحرف الذي يغادر إلا إذا أصبحت النافذة تفتقر إليه. تحتوي النافذة علىtبالضبط عندما تكون قيمةmissingتساوي 0.
الحل
المهم هو أعداد الأحرف في النافذة، وليس ترتيبها. حرّك الحافة اليمنى حتى تغطي النافذة t، ثم حرّك الحافة اليسرى ما دامت النافذة لا تزال تغطيه؛ ولا تعود أي من الحافتين إلى الوراء. يخبرك عدّاد الأحرف الناقصة بخطوة واحدة ما إذا كانت النافذة تغطي t.
وسّع نافذة من كل نقطة بداية
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
ثبّت موضع بداية ووسّع النافذة حرفًا واحدًا في كل مرة، مع الاحتفاظ بعدد مرات ظهور كل حرف. بعد كل خطوة، تحقّق من كل حرف من الأحرف u التي يستخدمها t. أول موضع نهاية يحقق الشرط يعطي أقصر نافذة تغطية تبدأ من هذا الموضع، لذا توقّف عنده. عالج مواضع البداية من اليسار إلى اليمين، ولا تستبدل الأفضل إلا بنافذة أقصر فعلًا، لذا عند التعادل تبقى النافذة التي تبدأ في الموضع الأيسر.
إذا لم توجد نافذة، فكل موضع بداية يقرأ حتى نهاية s: نحو n²/2 خطوة، أي 1.25 × 10^9 عندما يكون n = 5 × 10^4.
الخوارزمية
- احسب عدد مرات تكرار كل حرف يطلبه
t. - لكل
start، أفرغ جدول العدّ وحرّكendإلى اليمين، مع إضافةs[end]. - عندما تحتوي النافذة على عدد كافٍ من كل حرف، احتفظ بها إذا كان طولها أقصر تمامًا من الأفضل، وانتقل إلى بداية تالية.
- أعِد أفضل نافذة، أو
""إذا لم تغطِّ أي نافذة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]نافذة منزلقة تتحقق من كل حرف
الفكرة
إضافة أحرف إلى نافذة تغطي المطلوب تُبقيها كذلك، وإزالة أحرف من نافذة ينقصها شيء تُبقيها ناقصة. لذلك، بينما تتحرك البداية إلى اليمين، لا تتحرك نهاية أقصر نافذة تغطي المطلوب إلى اليسار أبدًا.
لا تفوتنا أي نافذة. لنأخذ أفضل نافذة، من L إلى R. لكي يتجاوز left الموضع L قبل أن يصل right إلى R، يجب أن تكون هناك نافذة أقصر تبدأ من L وتغطي t. لذلك، عندما يصل right إلى R، يؤدي تقليص النافذة إلى تحريك left حتى L وتسجيلها.
يتحرك كل طرف بحد أقصى n مرة، لكن كل عملية تحقق تقرأ ما يصل إلى u من القيم: O(n·u).
الخوارزمية
- احسب عدد النسخ التي يطلبها
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.
الحرف الذي يدخل بينما تكون قيمة need أكبر من 0 يسد فجوة، لذا تنخفض missing. والحرف الذي تؤدي إزالته إلى رفع قيمة need إلى ما فوق 0 يفتح فجوة، لذا ترتفع missing. لا يؤثر الفائض فيها أبدًا. عند استخدام banana مع t = aan، تصل missing إلى 0 أولًا عند bana، ويؤدي إسقاط b الزائد إلى بقاء ana مغطيةً للمطلوب.
يدخل كل حرف ويخرج مرة واحدة بتكلفة ثابتة: زمن 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. - استبدال أفضل نافذة عند تساوي الطول. في المثال الثاني، يؤدي ذلك إلى إرجاع
anaعند الفهرس 3. - استخدام
nطولًا لقيمة «غير موجود». عندما تكون الإجابة هي كاملs، يكون طولهاnأيضًا؛ لذا ابدأ منn+1. - جدول من 26 خانة مفهرسة بـ
c - 'a'. تقع الأحرف الكبيرة، كما في المثال الثالث، خارج نطاقه.
أسئلة شائعة3
ما هو التعقيد الزمني لمشكلة أقصر سلسلة فرعية تحتوي على جميع الأحرف؟
تعمل نافذة العداد الناقص بزمن O(n + m)، حيث إن n وm هما طولا s وt. يقرأ بناء الجدول t مرة واحدة، ويدخل كل حرف من s النافذة ويغادرها مرة واحدة على الأكثر. الذاكرة الإضافية هي عدّاد واحد لكل رمز حرفي.
لماذا لا تتحرك الحافة اليسرى إلى الخلف أبدًا؟
لا يمرّ الحدّ الأيسر بموقع إلا بعد أن تكون النافذة التي تبدأ عنده قد غطّت t، وكانت تلك النافذة أقصر نافذة تغطية من ذلك الموضع. وأي نافذة تبدأ من هناك وتنتهي في وقت لاحق ستكون أطول، لذا فإن الرجوع إلى الوراء لا يمكن أن يعثر على إجابة أفضل أبدًا.
ما الفرق بين مسألة أقصر سلسلة فرعية تحتوي على جميع الأحرف المطلوبة والعثور على ترتيبٍ مختلف للأحرف في سلسلة نصية؟
يحتوي الجناس الناقص على الأحرف نفسها الموجودة في t تمامًا، لذا يكون طول نافذته ثابتًا ويساوي m، وتنزلق خطوة واحدة في كل مرة. أما هنا، فتُسمح بأحرف إضافية، لذا يكون الطول جزءًا من الإجابة: تكبر النافذة حتى تحتوي على t، ثم تصغر ما دامت لا تزال تحتوي عليه.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def minWindow(s, t):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
s = "mappingtheplan" t = "nap"
الإخراج المتوقع
"plan"