Longest Valid Parentheses
لديك سلسلة نصية s تتكوّن فقط من المحرفين ( و). أوجد أطول سلسلة فرعية (مجموعة من المحارف المتتالية) تكون سليمة: يجب أن يكون لكل ( فيها محرف ) لاحق يغلقه، وأن تكون الأزواج متداخلة على نحو صحيح، كما في (()()). أعد طول هذه السلسلة الفرعية، أو 0 إذا لم يظهر حتى ().
الدالة
- sstring
- سلسلة من الأحرف ( و )
- تُرجعinteger
- طول أطول سلسلة فرعية سليمة التكوين، أو 0 إذا لم توجد أيٌّ منها
القيود
1 ≤ s.length ≤ 6 × 104- كل حرف في
sهو(أو).
أمثلة
- المدخلات
- s = "()(())"
- المخرجات
- 6
- الشرح
- السلسلة بأكملها سليمة التكوين:
()يتبعها(()). قطعتان سليمتا التكوين جنبًا إلى جنب تشكّلان قطعة واحدة سليمة التكوين، لذا فالإجابة هي الأحرف الستة كلها.
- المدخلات
- s = "())((())"
- المخرجات
- 4
- الشرح
- ليس للقوس
)عند الفهرس 2 قوسٌ مقابل، لذا لا يمكن لأي إجابة أن تتجاوزه، كما أن القوس(عند الفهرس 3 لا يُغلَق مطلقًا. أطول مقطع هو(())من الفهرس 4 إلى 7، وطوله 4، وهو أطول من()في البداية.
- المدخلات
- s = "))(("
- المخرجات
- 0
- الشرح
- يأتي كلا
)قبل كلا(، لذا لا يتم إغلاق أي(أبدًا. لا توجد سلسلة فرعية جيدة التكوين، والإجابة هي 0.
+21 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك أيضًا تحديد موضع بداية أطول سلسلة فرعية سليمة التكوين، واختيار الأسبق من اليسار عند وجود عدة سلاسل بالطول نفسه؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اقرأ سلسلة فرعية من اليسار إلى اليمين واحتفظ بقيمة توازن: +1 للقوس
(، و-1 للقوس). كيف تتغير قيمة التوازن في سلسلة فرعية سليمة التكوين، وماذا يخبرك القوس)الذي يجعلها أقل من الصفر عن كل سلسلة فرعية تمر به؟احتفظ بمكدّس لفهارس المحارف
(التي ما زالت مفتوحة. عندما يُغلق المحرف)المحرفَ الموجود في أعلى المكدّس، يبدأ المقطع سليم التكوين الذي ينتهي هنا مباشرةً بعد الفهرس الموجود الآن في أعلى المكدّس. ما الذي ينبغي أن يكون في المكدّس عندما لا يكون هناك أي محرف مفتوح؟ابدأ المكدس بالقيمة -1، أي بالفهرس الذي يسبق السلسلة مباشرةً. ادفع فهرس كل
(إلى المكدس. عند مواجهة)، أخرج عنصرًا من المكدس؛ إذا أصبح المكدس فارغًا الآن، فلن يمكن مطابقة هذا)أبدًا، لذا ادفع فهرسه ليصبح الأساس الجديد؛ وإلا، فإن طول المقطع الحالي هوiمطروحًا منه الفهرس الموجود في أعلى المكدس. احتفظ بأكبر طول للمقاطع التي تقيسها.
الحل
هناك أمران يجعلان هذه المسألة أصعب من فحص سلسلة واحدة. تتصل المقاطع الصحيحة عندما تتلامس، لذا فإن () و(()) المتجاورتين تُحسبان كمقطع واحد طوله 6. كما أن محرفًا شاردًا واحدًا، مثل ) في ())(())، يقطع السلسلة، فلا يمكن لأي إجابة أن تتجاوزه. يتطلب اختبار كل موضع بداية O(n²). والحل هو تذكّر الموضع الذي بدأ منه المقطع الحالي: إذ تنجز ذلك مكدسة من الفهارس مع علامة أساس في الأسفل بمرور واحد، كما تنجزه تمريرتان باستخدام عدّادات عادية فقط، من دون أي مكدسة.
أنشئ سلسلة فرعية تبدأ من كل موضع
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اقرأ سلسلة فرعية من اليسار إلى اليمين مع رصيد يزيد بمقدار 1 عند ( وينقص بمقدار 1 عند ). تكون السلسلة الفرعية سليمة التكوين بالضبط عندما لا ينخفض الرصيد أبدًا عن 0 وينتهي عند 0. والانخفاض إلى ما دون 0 يعني أن ) ظهرت دون وجود قوس مفتوح لإغلاقه.
لذا، ثبّت نقطة بداية وتحرك نحو اليمين، مع تحديث الرصيد حرفًا واحدًا في كل مرة. في كل مرة يعود فيها إلى 0، يكون المقطع من نقطة البداية إلى هنا سليم التكوين، وتسجّل طوله. وبمجرد أن ينخفض إلى ما دون 0، توقّف: ستظل ) هذه غير متطابقة في كل المقاطع الأطول التي تبدأ من هذه النقطة. لكل سلسلة فرعية سليمة التكوين نقطة بداية ما، وأنت تجرّب كل نقطة نهاية لها، لذا لن يفوتك شيء.
المشكلة هي التكلفة. في سلسلة تتكوّن من 59998 من ( يتبعها ()، لا ينخفض الرصيد أبدًا عن 0، لذا يمتد المسح من كل نقطة بداية حتى النهاية: نحو n²/2 = 1.8 × 10^9 خطوة عندما تكون n = 6 × 10^4. الاختبارات الكبيرة مبنية بهذه الطريقة. (أما التحقق من كل سلسلة فرعية من البداية بدلًا من توسيعها فسيكون أسوأ، O(n³).)
الخوارزمية
- عيّن
bestإلى 0. - لكل موضع بداية، عيّن
balanceإلى 0، وتقدّم بالنهاية من موضع البداية حتى آخر محرف. - أضف 1 عند
(واطرح 1 عند). - إذا كانت قيمة
balanceأقل من 0، فتوقّف عند موضع البداية هذا. وإذا كانت 0، فحدّثbestبطول المقطعend - start + 1. - أعِد
best.
def longestValidParentheses(s):
best = 0
for start in range(len(s)):
balance = 0
for end in range(start, len(s)):
balance += 1 if s[end] == "(" else -1
if balance < 0:
# A ')' without a partner: no longer run starts here
break
if balance == 0:
best = max(best, end - start + 1)
return bestمكدّس من الفهارس مع علامة أساسية
الفكرة
مألوفٌ استخدام مكدّس لمطابقة الأقواس: أضف كل ( إلى المكدّس، وأزِل عنصرًا منه مقابل كل ). تحتاج هنا أيضًا إلى الأطوال، لذا أضف الفهارس إلى المكدّس، واحتفظ بفهرس إضافي واحد في قاع المكدّس: القاعدة، أي الموضع الذي يسبق مباشرةً الجزء المتصل الذي أنت فيه. في البداية لم يُقرأ أي شيء، لذا تكون القاعدة -1.
عند (، أضف فهرسه إلى المكدّس. وعند )، أزِل عنصرًا من المكدّس. قد يحدث أحد أمرين. إذا أصبح المكدّس فارغًا الآن، فهذا يعني أنك أزلت القاعدة، لذا لم يكن لهذا ) ما يغلقه. لا يمكن لأي جزء فرعي سليم التكوين أن يتضمنه، ويصبح هو القاعدة الجديدة: أضف فهرسه إلى المكدّس. وإلا، يكون الفهرس المتبقي في القمة هو آخر محرف قبل الجزء المتصل الذي ينتهي عند i: إما ( لا يزال مفتوحًا أو القاعدة. كل ما يأتي بعده حتى i متطابق، ولا يمكن للجزء المتصل أن يمتد إلى اليسار أكثر، لذا يكون طوله i - top.
إليك ())((()):
i = 0،(: أضف 0. المكدّس[-1, 0].i = 1،): أزل 0. القمة هي -1، لذا يكون طول الجزء1 - (-1) = 2.i = 2،): أزل -1 ويصبح المكدّس فارغًا. ليس لهذا)قوس مقابل، لذا أضف 2 بوصفه القاعدة الجديدة. المكدّس[2].i = 3, 4, 5، ثلاثة أقواس(: أضفها. المكدّس[2, 3, 4, 5].i = 6،): أزل 5. القمة هي 4، لذا يكون طول الجزء6 - 4 = 2.i = 7،): أزل 4. القمة هي 3، لذا يكون طول الجزء7 - 3 = 4، وهي الإجابة.
القاعدة هي ما يجعل الأجزاء المتجاورة تندمج. في ()(())، طول الزوج الأول هو 1 - (-1) = 2، وعند القوس ) الأخير يُزال الفهرس 2 وتظهر -1 على القمة مجددًا، لذا يكون الطول 5 - (-1) = 6. أما القياس بدءًا من ( المطابق بدلًا من ذلك فسيعطي 4 ويفوّت () في المقدمة. يُضاف كل فهرس إلى المكدّس ويُزال منه مرة واحدة على الأكثر، لذا يكون المرور O(n)، ويمكن للمكدّس أن يحتوي على ما يصل إلى n+1 فهرسًا.
الخوارزمية
- ابدأ مكدسًا يحتوي على -1، واضبط
bestعلى 0. - لكل فهرس
i، ادفعiإلى المكدس إذا كانs[i]هو(. - إذا كان
)، فأزل عنصرًا واحدًا من المكدس. - إذا أصبح المكدس فارغًا الآن، فادفع
iليكون القاعدة الجديدة. وإلا، حدّثbestباستخدامi - top. - أعِد
best.
def longestValidParentheses(s):
# The bottom of the stack is the index just before the current run
stack = [-1]
best = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop()
if not stack:
# This ')' has no partner: it becomes the new base
stack.append(i)
else:
best = max(best, i - stack[-1])
return bestعدّ مرات الفتح والإغلاق على مرحلتين
الفكرة
لا يخبرك المكدس إلا بالمكان الذي بدأ منه المقطع الحالي. ويمكن لعدّادين أن يفعلا ذلك أيضًا. تحرّك من اليسار إلى اليمين، مع عدّ opens وcloses منذ آخر إعادة ضبط. عندما يتساوى العددان، يكون كل ما بين إعادة الضبط هذه والآن صحيح التكوين، وطوله 2 × closes. عندما يتجاوز closes العددَ الآخر، لا يكون لـ ) نظير، وفي اللحظة نفسها يكون المكدس قد فقد قاعدته، لذا أعد ضبط العدّادين إلى 0.
لا تكفي عملية مرور واحدة. فالقوس ( الذي لا يُغلَق يُبقي opens متقدمًا إلى الأبد، ولا يتساوى العددان مجددًا. في (()، ينتهي المرور من اليسار بوجود قوسين مفتوحين وقوس إغلاق واحد، ولا يعثر على شيء، رغم أن () موجودة هناك. لذا تحرّك مرة ثانية، من اليمين إلى اليسار، مع تبديل الأدوار: أعد الضبط عندما يتجاوز opens العددَ الآخر. عند القراءة بالعكس، تعطي (() قوس إغلاق، ثم قوس فتح (تساوٍ: الطول 2)، ثم قوس فتح يؤدي إلى إعادة الضبط. الإجابة هي الأكبر بين نتيجتي المرور.
لماذا يعثر المروران على كل مقطع: يحدّ أطول مقطعَ أحرفٌ لا يمكن أبدًا مطابقتها، أو طرفا السلسلة. إذا كان حدّه الأيسر قوس إغلاق زائدًا ) أو بداية السلسلة، فإن المرور من اليسار يعيد الضبط عند بداية المقطع، ويرى تساوي العددين عند نهايته. وإذا كان حدّه الأيسر قوس فتح زائدًا (، فلا يمكن أن يكون حدّه الأيمن )، لأن قوس الإغلاق هذا سيغلق قوس الفتح الزائد، وسيصبح المقطع أطول. لذا يكون الحد الأيمن قوس فتح زائدًا ( أو نهاية السلسلة، ويعثر المرور من اليمين على المقطع بالطريقة نفسها. يقرأ كل مرور السلسلة مرة واحدة باستخدام عددين صحيحين، لذا يكون الزمن O(n) والذاكرة الإضافية O(1).
الخوارزمية
- عيّن
bestإلى 0، وعيّنopensوclosesإلى 0. - امشِ من اليسار إلى اليمين، مع عدّ كل محرف. عندما يتساوى العدّان، حدّث
bestباستخدام2 × closes. عندما تكون قيمةclosesأكبر، أعد تعيين كليهما إلى 0. - أعد تعيين العدادين، ثم امشِ من اليمين إلى اليسار بالطريقة نفسها، باستثناء أنك تعيد التعيين عندما تكون قيمة
opensأكبر. - أعِد
best.
def longestValidParentheses(s):
best = 0
# Left to right: more ')' than '(' ends every run that started earlier
opens = closes = 0
for ch in s:
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * closes)
elif closes > opens:
opens = closes = 0
# Right to left: catches the runs that an unmatched '(' hid from the first pass
opens = closes = 0
for ch in reversed(s):
if ch == "(":
opens += 1
else:
closes += 1
if opens == closes:
best = max(best, 2 * opens)
elif opens > closes:
opens = closes = 0
return best
أخطاء شائعة وحالات حدّية
تعدّ معظم الإجابات الخاطئة الأزواج الصحيحة في مواضع غير صحيحة، أو تفقد بداية سلسلة.
- عدّ الأزواج المتطابقة في السلسلة كلها. تحتوي
())((())على 3 أزواج، لكنها ليست متجاورة كلها، والإجابة هي 4، لا 6. - قياس السلسلة بدءًا من
(المطابق. في()(())، يطابق آخر)الفهرس 2، ما يعطي 4 ويفوّت()التي تسبقه. قِس بدءًا من الفهرس المتبقي على المكدس بعد إزالة العنصر. - البدء بمكدس فارغ. عندئذٍ لا يجد أول
)في())ما يقيس المسافة انطلاقًا منه، كما أن)غير المطابقة تزيل عنصرًا من مكدس فارغ. تعالج القيمة الأساسية -1 المشكلتين. - تشغيل العدّادات في اتجاه واحد فقط. تُرجع
(()القيمة 0 من اليسار إلى اليمين، وتُرجع())القيمة 0 من اليمين إلى اليسار؛ والإجابة هي 2 في الحالتين. - إعادة ضبط العدّادات عندما تتساوى. تساوي العددين يعني أن السلسلة قد تستمر في النمو، كما في
()()؛ لذا لا تُعد ضبط العدّادات إلا عندما يتقدم أحد الجانبين. - في Lua وR، يبدأ ترقيم المواضع من 1، لذا تكون القيمة الأساسية الأولى 0، لا -1.
أسئلة شائعة4
ما هو التعقيد الزمني لمسألة أطول سلسلة من الأقواس المتطابقة؟
يقرأ كلٌّ من حل المكدّس وحل العدّاد ذي المرورين كل محرف عددًا ثابتًا من المرات، لذا يعملان في زمن O(n). يحتاج المكدّس إلى ذاكرة O(n) في أسوأ الحالات، مثل سلسلة تتكوّن فقط من (، بينما يحتاج العدّادان إلى O(1). تجربة كل نقطة بداية تستغرق O(n²).
لماذا يبدأ المكدس بـ -1؟
طول التتابع هو الفهرس الحالي مطروحًا منه الفهرس السابق مباشرةً لبداية التتابع. بالنسبة إلى تتابع يبدأ عند الفهرس 0، يكون ذلك الفهرس السابق -1، أي خطوة واحدة قبل السلسلة. دفع -1 أولًا يعني أن المكدس لا يكون فارغًا أبدًا عند قياس ) المطابقة، وعندما تزيل ) غير المطابقة هذا العنصر من المكدس، تصبح تلك ) هي الأساس الجديد.
هل يوجد حل باستخدام البرمجة الديناميكية لمسألة أطول سلسلة أقواس صحيحة؟
نعم. لتكن end[i] طول أطول سلسلة فرعية سليمة تنتهي عند الفهرس i؛ وتكون 0 عندما تكون s[i] هي (. إذا كانت s[i-1] هي (، فحينها end[i] = end[i-2] + 2. وإذا كانت )، فانظر إلى j = i - end[i-1] - 1، أي الحرف الذي يسبق السلسلة المنتهية عند i-1: عندما تكون s[j] هي (، فإنها تُحيط بتلك السلسلة، وتكون end[i] = end[i-1] + 2 + end[j-1]، حيث يضم الحد الأخير سلسلةً متصلة بها من اليسار. الإجابة هي أكبر قيمة لـ end[i]، بزمن وذاكرة O(n).
لماذا لا تكفي تمريرة واحدة باستخدام العدّادات؟
لا تعيد عملية المرور من اليسار إلى اليمين التعيين إلا عندما يتجاوز عدد ) عدد (. إن وجود ( إضافية لا تُغلق يُبقي العددين مختلفين حتى نهاية السلسلة، لذا لا تراهما عملية المرور متساويين أبدًا. في (() تنتهي العملية بوجود قوسَي فتح وقوس إغلاق واحد، ولا تعثر على شيء. والقراءة من اليمين إلى اليسار تتعامل مع ( الزائدة بالطريقة نفسها التي تتعامل بها عملية المرور الأولى مع ) زائدة، لذا تغطي عمليتا المرور معًا كل سلسلة.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def longestValidParentheses(s):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
s = "()(())"
المتوقع
6