Valid Parentheses
لديك سلسلة نصية s تتكوّن فقط من رموز الأقواس ( و) و[ و] و{ و}. أعد true عندما تكون الأقواس متوازنة: كل قوس إغلاق يغلق أحدث قوس ما زال مفتوحًا، ويكون القوسان من النوع نفسه، ولا يبقى أي قوس مفتوح في النهاية. وإلا فأعد false.
الدالة
- sstring
- سلسلة الأقواس المراد التحقق منها
- تُرجعboolean
- ما إذا كانت الأقواس متوازنة
القيود
1 ≤ s.length ≤ 104sيحتوي فقط على الأحرف(و)و[و]و{و}.
أمثلة
- المدخلات
- s = "[]{}()"
- المخرجات
- true
- الشرح
- تقف ثلاثة أزواج جنبًا إلى جنب، ويُغلَق كل زوج مباشرةً بعد فتحه.
- المدخلات
- s = "{[()()]}"
- المخرجات
- true
- الشرح
- يُغلَق الزوجان المستديران داخل الزوج المربّع، الذي يُغلَق داخل الزوج المعقوف. كل مُغلِق يطابق أحدث مُفتتِح لا يزال مفتوحًا.
- المدخلات
- s = "{(})"
- المخرجات
- false
- الشرح
- يأتي
}بينما لا يزال القوس(الذي فُتح بعده مفتوحًا، لذا فهو يغلق نوعًا خاطئًا من الأقواس.
سؤال إضافي
إذا كانت السلسلة تحتوي على أقواس مستديرة فقط، فهل يمكنك التحقق منها باستخدام عدّاد واحد بدلًا من المكدس، وبمساحة إضافية O(1)؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اقرأ السلسلة من اليسار إلى اليمين. عندما يصل قوس إغلاق، أيُّ قوس فتح يُسمح له بإغلاقه؟
لا يمكنه إغلاق سوى قوس الفتح الذي فُتح أخيرًا وما زال مفتوحًا. آخر ما فُتح هو أول ما يُغلق: هذا هو بالضبط الترتيب الذي يحافظ عليه المكدس.
ادفع كل قوس افتتاحي إلى المكدس. عند مصادفة قوس إغلاق، يجب ألا يكون المكدس فارغًا، ويجب أن يكون العنصر الموجود في قمته من النوع نفسه؛ أزِله وتابع. عند انتهاء السلسلة، تكون متوازنة فقط إذا كان المكدس فارغًا.
الحل
عدّ الأقواس ليس كافيًا: {(}) يحتوي على قوس فتح وقوس إغلاق من كل نوع، ومع ذلك فهو غير صحيح، لأن الترتيب مهم. يحتفظ المكدس بالأقواس التي لم تُغلق بعد، بالترتيب الذي فُتحت به، لذا فإن المرور مرة واحدة باستخدام مكدس يحدد صلاحية السلسلة بأكملها.
أزِل الأزواج المتطابقة بشكل متكرر
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
كل سلسلة متوازنة تحتوي على زوج داخلي لا يوجد شيء بين قوسيه، مثل () داخل {[()]}. حذف زوج متجاور ومتطابق لا يغيّر أبدًا ما إذا كانت السلسلة متوازنة. لذا كرّر عمليات الحذف حتى تمر جولة كاملة دون حذف أي شيء: تتقلص السلسلة المتوازنة إلى سلسلة فارغة، بينما تتوقف السلسلة غير المتوازنة مع بقاء محارف فيها، كما هو الحال في {(}) منذ البداية.
تفحص كل جولة السلسلة بأكملها وتبني نسخة جديدة، والسلسلة المتداخلة مثل (((...))) تفقد زوجًا واحدًا في كل جولة. يتطلب ذلك ما يصل إلى n/2 جولة من العمل بتعقيد O(n)، أي O(n²) إجمالًا.
الخوارزمية
- احذف كلًا من
()و[]و{}من السلسلة النصية. - إذا لم تحذف تلك الجولة شيئًا، فتوقّف.
- وإلا، كرّر العملية على السلسلة النصية الأقصر.
- أعِد
trueإذا انتهى الأمر بالسلسلة النصية فارغة، وfalseإذا بقي أي قوس.
def isValid(s):
while True:
# Delete every adjacent matched pair in one round.
shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
if shorter == s:
break # nothing left to delete
s = shorter
return s == ""مرور واحد باستخدام مكدس
الفكرة
يجب أن يغلق القوس الختامي القوسَ الذي فُتح مؤخرًا وما زال مفتوحًا. يُغلق القوس الذي فُتح أخيرًا أولًا، وهذا الترتيب، آخر ما يدخل أول ما يخرج، هو بالضبط ما يحافظ عليه المكدس.
أضِف إلى المكدس القوس الختامي الذي ينتظره كل قوس افتتاحي. يجب بعد ذلك أن يطابق القوس الختامي العنصر الموجود أعلى المكدس. يعني المكدس الفارغ أنه لا يوجد ما يمكن إغلاقه؛ أما اختلاف العنصر الموجود في الأعلى فيعني أنه يغلق نوعًا خاطئًا، كما يحدث مع } في {(}) بينما يكون ) في الأعلى. في النهاية، أي شيء متبقٍ في المكدس، كما في ((، قد فُتح ولم يُغلق قط. يُضاف كل محرف إلى المكدس أو يُزال منه مرة واحدة: زمن O(n)، وبحد أقصى n من العناصر في المكدس.
الخوارزمية
- أنشئ مكدسًا فارغًا.
- عند وجود قوس فتح، ادفع قوس الإغلاق المطابق إلى المكدس.
- عند وجود قوس إغلاق، أعد
falseإذا كان المكدس فارغًا أو كان العنصر في قمته محرفًا مختلفًا؛ وإلا فأزل العنصر من القمة. - بعد المحرف الأخير، أعد
trueفقط إذا كان المكدس فارغًا.
def isValid(s):
closers = {'(': ')', '[': ']', '{': '}'}
stack = []
for ch in s:
if ch in closers:
stack.append(closers[ch])
elif not stack or stack.pop() != ch:
return False
return not stack
أخطاء شائعة وحالات حدّية
- عدّ كل نوع من الأقواس. يحتوي
{(})على أعداد متطابقة، لكنه يظل غير صالح، بينما يفشل)(بسبب الترتيب وحده. - محاولة إخراج عنصر من مكدس فارغ. يجب أن تُرجع سلسلة تبدأ بقوس إغلاق، مثل
}أو)]}، القيمةfalseبدلًا من أن يتعطل البرنامج. - تجاوز الفحص النهائي. لا يواجه
(([{قوس إغلاق خاطئًا أبدًا، لذا فإن العناصر المتبقية في المكدس وحدها هي ما يوضح أنه غير صالح. - الاعتماد على الطول. الطول الفردي غير صالح دائمًا، لكن الطول الزوجي لا يثبت شيئًا: كل من
(]و())(غير صالح. - في أسلوب الإزالة، تمرير الأقواس إلى تعبير نمطي أو نمط Lua من دون تهريبها. لـ
(و[معنى خاص هناك؛ استخدم استبدالًا للنص الحرفي.
أسئلة شائعة3
ما هو التعقيد الزمني لمشكلة الأقواس المتطابقة؟
يعمل الحل باستخدام المكدس بزمن O(n)، لأن كل محرف يُضاف إلى المكدس أو يُزال منه مرة واحدة على الأكثر. ويستخدم مساحة O(n) في أسوأ الحالات، عندما تكون السلسلة مكوّنة من رموز فتح فقط. أما إزالة الأزواج المتطابقة مرارًا وتكرارًا فتستغرق زمنًا قدره O(n²)، لأن السلسلة المتداخلة بعمق تفقد زوجًا واحدًا فقط في كل جولة.
لماذا تُستخدم المكدّسة للتحقق من صحة الأقواس؟
تتداخل الأقواس، لذا يجب إغلاق القوس الذي فُتح أخيرًا أولًا. تحتفظ المكدسة بهذا القوس في الأعلى، حيث يمكنك قراءته وإزالته في زمن ثابت، ما يُبقي الفحص بأكمله عند O(n).
هل السلسلة النصية الفارغة أقواس صالحة؟
نعم. السلسلة الفارغة لا تحتوي على أي قوس غير متطابق، لذا فهي متوازنة: يظل المكدس فارغًا، ولا يوجد ما تزيله حلقة الإزالة. في هذه المسألة، تحتوي s دائمًا على حرف واحد على الأقل.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def isValid(s):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
وسيط
s = "[]{}()"الإخراج المتوقع
true