Generate Parentheses
تكون سلسلة الأقواس سليمة التكوين عندما لا يتجاوز عدد ) عدد ( عند قراءتها من اليسار إلى اليمين، ويتساوى العددان في النهاية. لذا فإن (())() سليمة التكوين، بينما ())( ليست كذلك: فمحرفها الثالث يغلق زوجًا لم يُفتح قط.
أُعطِي عددًا صحيحًا n، وأعِد كل سلسلة سليمة التكوين تتكون من n قوس فتح وn قوس إغلاق، مرتبة ترتيبًا معجميًا، بحيث يأتي ( قبل ).
الدالة
- ninteger
- عدد أزواج الأقواس
- تُرجعstring-array
- كل سلسلة سليمة التكوين مكوّنة من n أزواج، بترتيب معجمي
القيود
1 ≤ n ≤ 8- عند
n = 8، يكون الجواب 1,430 سلسلة.
أمثلة
- المدخلات
- n = 3
- المخرجات
- ["((()))", "(()())", "(())()", "()(())", "()()()"]
- الشرح
- تنتج ثلاثة أزواج خمس سلاسل سليمة التكوين. تفتح
((()))الأزواج الثلاثة كلها أولًا، لذا تأتي أولًا عند الترتيب؛ أما()()()فتغلق كل زوج فورًا، لذا تأتي أخيرًا.
- المدخلات
- n = 1
- المخرجات
- ["()"]
- الشرح
- يحتوي أحد الترتيبين على سلسلة سليمة التكوين. أما الترتيب الآخر الوحيد،
)(، فيُغلق قبل فتح أي شيء.
سؤال إضافي
هل يمكنك عدّ السلاسل سليمة التكوين المكوّنة من n أزواج دون توليدها؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
اقرأ سلسلةً من اليسار إلى اليمين، وأبقِ عدد الأزواج المفتوحة. ما الخطأ الذي حدث عندما ينخفض هذا العدد إلى أقل من الصفر؟
أنشئ السلسلة حرفًا واحدًا في كل مرة. يمكنك إضافة
(ما دمت قد أضفت أقل منnمنها، وإضافة)ما دام عدد أحرف)التي أضفتها أقل من عدد أحرف(. يمكن دائمًا إكمال سلسلة بُنيت بهذه الطريقة.استخدم الاستدعاء الذاتي مع عدّادين،
openedوclosed. جرّب فرع(قبل فرع)، واحذف كل محرف بعد عودة الاستدعاء، واحفظ السلسلة عندما يصل طولها إلى2n. تجربة(أولًا تُبقي الناتج مرتبًا.
الحل
2n يكون سليم البنية: 1,430 من أصل 65,536 عندما تكون n = 8. ابنِ كل سلسلة من اليسار إلى اليمين، وأضف حرفًا فقط عندما يظل من الممكن إكمال البادئة. ويحدد عدّادان ذلك، كما أن تجربة ( قبل ) تجعل السلاسل مرتبة.أنشئ كل سلسلة نصية، ثم تحقّق منها
الفكرة
املأ المواضع 2n بكل التوليفات الممكنة من ( و)، أي 4^n سلسلة، ثم احتفظ بالسلاسل السليمة التكوين. للتحقق من سلسلة، مرّ عليها مع تتبّع رصيد: أضف 1 عند (، واطرح 1 عند ). تكون السلسلة سليمة التكوين عندما لا ينخفض الرصيد أبدًا عن 0 وينتهي عند 0. إن وضع ( قبل ) في كل موضع يسرد السلاسل بترتيب تصاعدي.
تستغرق عملية التحقق من كل سلسلة O(n). عندما تكون n = 8، فهذا يعني 65,536 سلسلة مقابل 1,430 إجابة، لذا يُهدر نحو 98% من العمل، ويتضاعف العدد أربع مرات مع كل زوج إضافي.
الخوارزمية
- احتفظ بمخزن مؤقت يضم
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، لا يمكن لفرع (( إلا أن يغلق القوسين، لينتج (())، ولا يمكن لفرع () إلا أن يفتح قوسًا ويغلقه، لينتج ()(). كل سلسلة تمثل مسارًا واحدًا في الشجرة، لذا تظهر مرة واحدة، ويأتي فرع ( أولًا، لذا يكون الإخراج مرتبًا.
كل ورقة هي إجابة، لذا يتناسب العمل مع حجم المخرجات: O(4^n / √n).
الخوارزمية
- احتفِظ بالسلسلة الجاري بناؤها وبعدادَين،
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 أو أعلى في كل خطوة. - تجربة
)قبل(. فتظهر السلاسل الصحيحة بترتيب عكسي. - حفظ المخزن المؤقت المشترك بدلًا من نسخة منه، عندما تكون القوائم أو أدوات إنشاء السلاسل قابلة للتغيير. عندها تعرض كل إجابة محفوظة المخزن المؤقت نفسه، الذي تُفرغه عملية التراجع مرة أخرى.
- تحديد حجم مصفوفة نتائج ثابتة بناءً على تخمين صغير. لدى
n = 8عدد 1,430 إجابة.
أسئلة شائعة3
ما هو التعقيد الزمني لتوليد الأقواس؟
ينتج التراجع الخلفي C(n) = (2n)! / ((n+1)! n!) سلسلة، وهو عدد كاتالان، وينمو مثل 4^n / (n^1.5 √π). يستغرق إنشاء كل سلسلة ونسخها O(n)، لذا يكون الزمن 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 علاقة كاتالان التكرارية.
هل يمكن حلّ مسألة توليد الأقواس دون استخدام الاستدعاء الذاتي؟
نعم. احتفظ بمكدس من الحالات الجزئية، كلٌّ منها سلسلة نصية تتضمن العدّادين، ووسّع كل حالة باستخدام القاعدتين نفسيهما. أضف امتداد ) إلى المكدس قبل امتداد (، لكي يُسحب امتداد ( أولًا، ويبقى الناتج مرتبًا.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def generateParenthesis(n):
# اكتب الكود هنااختبار #1
اختبار #2
وسيط
n = 3
الإخراج المتوقع
["((()))", "(()())", "(())()", "()(())", "()()()"]