Generate Parentheses
تكون سلسلة الأقواس مستوفية للشروط عندما لا يتجاوز عدد ) عدد ( عند قراءتها من اليسار إلى اليمين، ويتساوى العددان في النهاية. لذلك، فإن (())() مستوفية للشروط، بينما ())( ليست كذلك: فحرفها الثالث يغلق زوجًا لم يُفتح قط.
يُعطى لك عدد صحيح n. أعد كل سلسلة مستوفية للشروط مكوّنة من n قوس فتح وn قوس إغلاق، مرتبة ترتيبًا معجميًا، حيث يأتي ( قبل ).
الدالة
- ninteger
- عدد أزواج الأقواس
- تُرجعstring-array
- كل سلسلة سليمة التكوين مكوّنة من n أزواج، بترتيب معجمي
القيود
1 ≤ n ≤ 8- بالنسبة إلى
n = 8، يحتوي الحل على 1,430 سلسلة.
أمثلة
- المدخلات
- n = 3
- المخرجات
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
- الشرح
- يمكن ترتيب ثلاثة أزواج بخمس طرق سليمة التكوين. تفتح
((()))الأزواج الثلاثة قبل إغلاق أيٍّ منها، وبما أن(يأتي أولًا في الترتيب، فإنه يتصدر القائمة؛ أما()()()فيغلق كل زوج فورًا، ويأتي في النهاية.
- المدخلات
- n = 1
- المخرجات
- ["()"]
- الشرح
- لدى زوج واحد ترتيب صحيح واحد. والسلسلة الأخرى الوحيدة المكوّنة من
(واحدة و)واحدة هي)(، حيث يُغلَق القوس قبل فتح أي شيء.
+10 اختبارات مخفية عند الإرسال
سؤال إضافي
هل يمكنك حساب عدد السلاسل ذات الأقواس المتوازنة لـ n من الأزواج دون توليدها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اقرأ سلسلة من اليسار إلى اليمين، وأحصِ عدد الأزواج المفتوحة. ما الخطأ الذي حدث عندما ينخفض هذا العدد إلى ما دون الصفر؟
أنشئ السلسلة حرفًا واحدًا في كل مرة. يمكنك إضافة
(ما دمت قد وضعت أقل منnمنها، وإضافة)ما دمت قد وضعت عددًا أقل من)مقارنةً بـ(. يمكن دائمًا إكمال سلسلة أُنشئت بهذه الطريقة.استخدم الاستدعاء الذاتي مع عدّادين،
openedوclosed. جرّب فرع(قبل فرع)، وأزل كل محرف بعد عودة الاستدعاء، واحفظ السلسلة عندما يصل طولها إلى2n. تجربة(أولًا تُبقي المخرجات مرتبة.
الحل
نسبة صغيرة فقط من السلاسل ذات الطول 2n تكون صحيحة التنسيق: 5 من أصل 64 سلسلة عندما تكون n = 3، و1,430 من أصل 65,536 عندما تكون n = 8. تقوم الفكرة التي تحل المشكلة على بناء السلسلة من اليسار إلى اليمين، وإضافة حرف يحافظ على صحتها فقط، بحيث لا يدخل البحث أبدًا في فرع لا يمكن إكماله. يحدد عدّادان ما يُسمح به: عدد أحرف ( التي وضعتها، وعدد أحرف ). وتجربة ( قبل ) في كل خطوة تجعل السلاسل مرتبة مسبقًا.
أنشئ كل سلسلة نصية، ثم تحقّق منها
الفكرة
الطريقة المباشرة هي ملء المواضع 2n بكل الطرق الممكنة والاحتفاظ بالسلاسل المتوازنة. يشغل كل موضع ( أو )، لذا يوجد 2^(2n) = 4^n سلسلة. تضع دالة递归 ( في الموضع التالي، ثم تستدعي نفسها، وبعد ذلك تضع ) هناك وتستدعي نفسها مرة أخرى، ويخضع كل تسلسل مكتمل لفحص.
يتتبع الفحص السلسلة باستخدام رصيد: زائد 1 عند (، وناقص 1 عند ). تكون السلسلة متوازنة عندما لا يقل الرصيد عن 0 أبدًا وينتهي عند 0. والانخفاض إلى ما دون 0 يعني وجود ) من دون قوس مفتوح لإغلاقه، كما في المحرف الثالث من ())(.
تجربة ( قبل ) في كل موضع تسرد السلاسل بترتيب معجمي، لأن ( يسبق ) في الترتيب. لذا تكون السلاسل المحتفظ بها مرتبة بالفعل.
التكلفة هي 4^n سلسلة، يُفحص كل منها في O(n). عندما تكون n = 8، فهذا يعني 65,536 سلسلة مقابل 1,430 إجابة، أي إن نحو 98% من العمل يذهب هدرًا. تنتهي العملية هنا لأن n لا يتجاوز 8، لكن العدد يتضاعف أربع مرات مع كل زوج إضافي، كما أنها تواصل إنشاء سلاسل تبدأ بـ ) رغم أن المحرف الأول يستبعدها بالفعل.
الخوارزمية
- احتفظ بمخزن مؤقت من
2nمحرفًا وقائمة للإجابات. - اكتب
fill(pos). إذا كانتposتساوي2n، فتحقّق من المخزن المؤقت واحفظه إذا كان صحيح التكوين. - وإلا، ضع
(عندposواستدعِfill(pos + 1)، ثم ضع)هناك واستدعِها مرة أخرى. - للتحقق من سلسلة، أضف 1 لكل
(واطرح 1 لكل). ارفضها فورًا إذا أصبح الرصيد أقل من 0، أو إذا لم ينتهِ عند 0. - استدعِ
fill(0)وأعِد السلاسل المحفوظة، المرتبة مسبقًا.
def generateParenthesis(n):
result = []
path = []
def is_balanced(text):
balance = 0
for ch in text:
balance += 1 if ch == "(" else -1
if balance < 0:
return False # a ")" with nothing open to close
return balance == 0
def fill():
if len(path) == 2 * n:
text = "".join(path)
if is_balanced(text):
result.append(text)
return
for ch in "()": # "(" first keeps the output sorted
path.append(ch)
fill()
path.pop()
fill()
return resultالتراجع عن عدد مرات الفتح والإغلاق
الفكرة
انقل التحقّق إلى عملية البناء. يمكن أن تنمو البادئة لتصبح سلسلة صحيحة التكوين بالضبط عندما تتحقق قاعدتان: ألا تستخدم أكثر من n من الأقواس المفتوحة، وألا تحتوي أبدًا على عدد من ) أكبر من عدد (. لذا يمكنك في كل خطوة إضافة ( ما دام opened < n، وإضافة ) ما دام closed < opened. عندما يصل طول السلسلة إلى 2n، يكون كلا العددين n وتكون السلسلة صحيحة التكوين، ولا يبقى شيء للتحقق منه.
إليك الشجرة كاملةً عندما تكون n = 2. لا يُسمح من السلسلة الفارغة إلا بـ (، إذ لا يوجد قوس مفتوح بعد. ومن ( يُسمح بكليهما. في فرع ((، تكون قيمة opened قد بلغت 2 بالفعل، لذا لا يلائم إلا )، مرتين، فنحصل على (()). أما في فرع ()، فلا يوجد قوس مفتوح، لذا لا يلائم إلا (، ثم )، فنحصل على ()(). ينتهي كل فرع بإجابة: فلا يبني البحث سلسلةً يضطر إلى التخلص منها.
لا تُفوَّت أي إجابة. فكل بادئة لسلسلة صحيحة التكوين تلتزم بالقاعدتين، لذا لا يرفض البحث الحرف الذي تحتاج إليه السلسلة بعد ذلك، وتُنتَج كل سلسلة مرة واحدة، لأن حروفها ترسم مسارًا واحدًا عبر الشجرة. ويسير الترتيب كما في النهج الأول: تختلف سلسلتان لأول مرة عند النقطة التي يتفرع فيها مسارهما، ويُستكشف فرع ( هناك أولًا.
كل ورقة هي إجابة، وعدد الإجابات لـ n من الأزواج هو عدد كاتالان C(n)، الذي ينمو وفق 4^n / (n^1.5 √π). تقع كل عقدة داخلية على مسار إلى ورقة واحدة على الأقل، لذا يوجد على الأكثر 2n من العقد الداخلية لكل إجابة، كما أن نسخ إجابة يكلّف O(n). الإجمالي هو O(n × C(n)) = O(4^n / √n): عند n = 8، تُبنى 1,430 سلسلة مباشرةً بدلًا من التحقق من 65,536 سلسلة.
الخوارزمية
- احتفظ بالسلسلة التي يجري إنشاؤها، وبعدادين هما
openedوclosed، وكلاهما يساوي 0. - إذا كان طول السلسلة
2n، فاحفظ نسخة منها وأعِدها. - إذا كان
opened < n، فأضف(، واستدعِ الدالة递归 معopened + 1، ثم أزِله. - إذا كان
closed < opened، فأضف)، واستدعِ الدالة递归 معclosed + 1، ثم أزِله. - ابدأ من السلسلة الفارغة وأعِد السلاسل المحفوظة، وهي مرتبة مسبقًا لأن
(يُجرَّب أولًا.
def generateParenthesis(n):
result = []
path = []
def backtrack(opened, closed):
if len(path) == 2 * n:
result.append("".join(path))
return
# "(" sorts before ")", so trying it first keeps the output sorted
if opened < n:
path.append("(")
backtrack(opened + 1, closed)
path.pop()
if closed < opened: # only close a pair that is open
path.append(")")
backtrack(opened, closed + 1)
path.pop()
backtrack(0, 0)
return result
أخطاء شائعة وحالات حدّية
تُختزل القواعد في مقارنتين، لذا تكمن الأخطاء في هاتين المقارنتين وفي ترتيب الفرعين.
- السماح بـ
)عندما يكونclosed < nبدلًا منclosed < openedينشئ سلاسل مثل())(، التي تغلق زوجًا لم يُفتح أصلًا. - إن التحقق فقط من أن السلسلة تحتوي على العدد نفسه من
(و)يقبل)(. يجب أن يظل التوازن 0 أو أعلى في كل خطوة، وليس عند النهاية فقط. - تجربة
)قبل(تنتج السلاسل الصحيحة بترتيب معكوس، فتفشل المقارنة مع الإجابة المرتبة. - حفظ المخزن المؤقت المشترك بدلًا من نسخة منه، في لغة تكون فيها القوائم أو منشئات السلاسل قابلة للتغيير: حينها تشير كل إجابة محفوظة إلى المخزن المؤقت نفسه، الذي تفرغه عملية التراجع مجددًا.
- تحديد حجم مصفوفة النتائج الثابتة ليكون
2nإجابة، أو اختيار أي رقم صغير بالتخمين: عندما تكونn = 8يكون هناك 1,430 إجابة. كبّر المصفوفة أو احسب عدد كاتالان أولًا.
أسئلة شائعة4
ما التعقيد الزمني لتوليد الأقواس؟
يُخرج حلّ التراجع عدد كاتالان C(n) = (2n)! / ((n+1)! n!) من السلاسل، وينمو هذا العدد مثل 4^n / (n^1.5 √π). طول كل سلسلة هو 2n، ولا يهدر البحث أي فرع، لذا يكون الزمن الكلي O(4^n / √n). المساحة الإضافية هي O(n) للسلسلة الحالية ومكدس الاستدعاءات، بالإضافة إلى المخرجات.
كم عدد سلاسل الأقواس الصحيحة المكوّنة من n أزواج؟
أعداد كاتالان الدقيقة من الرتبة n: 1، 2، 5، 14، 42، 132، 429 و1,430 عندما تتراوح قيمة n من 1 إلى 8. يمكن فهم ذلك بهذه الطريقة: كل سلسلة سليمة الصياغة هي ( + A + ) + B، حيث يقابل ( الأول )، وتكون A وB سليمتَي الصياغة، وبينهما n-1 زوجًا. وبجمع الاحتمالات بحسب حجم A نحصل على علاقة كاتالان التراجعية.
لماذا يضمن أن يكون <code>closed</code> أصغر من <code>opened</code> أن تكون السلسلة صالحة؟
تكون السلسلة غير صحيحة تحديدًا عندما يظهر ) من دون وجود ( غير مطابق قبله، أي عندما يتجاوز عدد ) عدد (. إن السماح بـ ) فقط عندما يكون closed < opened يمنع حدوث ذلك تمامًا، والسماح بـ ( فقط عندما يكون opened < n يجعل كلا العددين يصلان إلى n عند طول 2n. تصف القاعدتان معًا كل بادئة من سلسلة سليمة التكوين.
هل يمكن حل مسألة توليد الأقواس دون استخدام الاستدعاء التكراري؟
نعم. احتفِظ بمكدّس للحالات الجزئية، كل حالة عبارة عن سلسلة نصية تحتوي على العدادين، ووسّع الحالة باستخدام القاعدتين نفسيهما. إذا دفعت امتداد ) إلى المكدّس قبل امتداد (، فسيُسحب امتداد ( أولًا، وسيبقى الناتج مرتبًا. العمل هو نفسه؛ لكن إدارة الحالة تنتقل من مكدّس الاستدعاءات إلى مكدّسك الخاص.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def generateParenthesis(n):
# اكتب الكود هناالحالة 1
الحالة 2
المدخلات
n = 3
المتوقع
["((()))", "(()())", "(())()", "()(())", "()()()"]