Letter Combinations of a Phone Number

Q: ما هو التعقيد الزمني لمسألة تركيبات أحرف رقم الهاتف؟

إنه O(4^n · n) بالنسبة إلى n من الأرقام: يمكن أن يكون هناك 4^n سلسلة، عندما يكون كل رقم 7 أو 9، وتستغرق كتابة كل منها n خطوة. ومع المفاتيح ذات الأحرف الثلاثة فقط، يكون التعقيد O(3^n · n) . لا يمكن لأي حل أن يكون أفضل، لأن هذا هو حجم المخرجات. يحتاج التراجع إلى مساحة إضافية O(n) إلى جانب المخرجات.

متوسطالتراجع

+10

على لوحة مفاتيح الهاتف، يحمل كل رقم من 2 إلى 9 بضعة أحرف: 2 هو abc، و3 هو def، و4 هو ghi، و5 هو jkl، و6 هو mno، و7 هو pqrs، و8 هو tuv، و9 هو wxyz.

تحصل على سلسلة digits. اختر حرفًا واحدًا لكل رقم، مع الحفاظ على ترتيب الأرقام، فتحصل على سلسلة يمكن كتابتها باستخدام المفاتيح. أعد كل هذه السلاسل مرتبة ترتيبًا معجميًا (ترتيب القاموس). بالنسبة إلى "23"، هناك تسع سلاسل، من "ad" إلى "cf".

الدالة

letterCombinations(digits: string) → string-array

digitsstring: الأرقام التي تم الضغط عليها، وكلٌّ منها من 2 إلى 9
تُرجعstring-array: كل سلسلة يمكن للمفاتيح كتابتها، بترتيب معجمي

القيود

1 ≤ digits.length ≤ 4
كل محرف في digits هو رقم من 2 إلى 9.
تحتوي الإجابة على 256 سلسلة على الأكثر.

أمثلة

المدخلات: digits = "23"
المخرجات: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
الشرح: يوفّر الرقم 2 الأحرف a وb وc، ويوفّر الرقم 3 الأحرف d وe وf. يقترن كل حرف أول بكل حرف ثانٍ، لذا توجد 3 × 3 = 9 سلاسل، ويؤدي سردها مع تغيّر الحرف الأول بأبطأ وتيرة إلى إبقائها مرتبة.

المدخلات: digits = "94"
المخرجات: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
الشرح: يتكوّن العدد 9 من أربعة أحرف، ويتكوّن العدد 4 من ثلاثة أحرف، لذا فهناك 4 × 3 = 12 سلسلة. تسبق السلاسل الثلاث التي تبدأ بـ w أول سلسلة تبدأ بـ x.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

لنفترض أنك لا تريد إلا التركيبات التي تُشكّل كلمات حقيقية في القاموس. كيف يمكنك تجنّب إنشاء جميع السلاسل النصية البالغ عددها 4^n أولًا؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

لا يمكن تخطي أي شيء هنا: فالإجابة نفسها تحتوي على ما يصل إلى 4^n من السلاسل، لذا فإن كل حل صحيح يبذل هذا القدر على الأقل من العمل في كتابتها. ما يختبره السؤال هو قدرتك على توليد مجموعة من الخيارات بطريقة منهجية، من دون إغفال أي خيار أو تكراره. هذا هو التراجع بأبسط صوره: شجرة قرارات لها مستوى لكل رقم، يجري اجتيازها بترتيب العمق أولًا، حيث تمثل كل ورقة إجابة.

أنشئ السلاسل النصية رقمًا واحدًا في كل مرة

الفكرة

ابنِ الإجابات رقمًا واحدًا في كل مرة. ابدأ بقائمة تحتوي على سلسلة نصية فارغة واحدة. بالنسبة إلى "23"، يحوّل الرقم 2 القائمة إلى a وb وc. ثم يضيف الرقم 3 إلى كل واحدة من هذه السلاسل الثلاث d وe وf، ما ينتج تسع سلاسل طول كل منها 2. بعد الرقم الأخير، تحتوي القائمة على كل الإجابات.

يكون الترتيب مرتبًا تلقائيًا. لنفترض أن القائمة مرتبة قبل معالجة رقم. تمدّد البادئات بالترتيب نفسه، وكل بادئة بحروف المفتاح من اليسار إلى اليمين. تظل السلسلة ذات البادئة الأسبق في المقدمة، وتُرتَّب السلاسل ذات البادئة نفسها بحسب الحرف الجديد، أي بترتيب القاموس.

تعتمد الكلفة على حجم الإجابة. إذا كان لدينا n من الأرقام، فستحتوي القائمة الأخيرة على ما يصل إلى 4^n سلسلة طول كل منها n، وستحتوي كل القوائم السابقة مجتمعةً على نصف هذا العدد على الأكثر من السلاسل، وكلها أقصر. أما العيب فهو استهلاك الذاكرة: أثناء بناء مستوى، يظل المستوى السابق بأكمله محفوظًا أيضًا، بما في ذلك كل بادئة قصيرة ستتخلص منها.

الخوارزمية

ابدأ بـ combos = [""]، أي ببادئة فارغة واحدة.
لكل رقم، أنشئ قائمة جديدة: أضف prefix + letter لكل بادئة في combos ولكل حرف على مفتاح ذلك الرقم.
استبدل combos بالقائمة الجديدة.
بعد الرقم الأخير، أعد combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

التراجع عبر شجرة القرار

الفكرة

فكّر في الإجابة على هيئة شجرة قرارات. الجذر سلسلة نصية فارغة. بالنسبة إلى "23"، له ثلاثة أبناء، a وb وc، واحد لكل حرف من أحرف 2. ولكل واحد من هذه الأبناء ثلاثة أبناء خاصين به، واحد لكل حرف من أحرف 3. تحتوي الشجرة على مستوى لكل رقم، والأوراق التسع، من ad إلى cf، هي الإجابات بالضبط.

يمرّ التراجع عبر تلك الشجرة بعمق باستخدام مخزن مؤقت واحد، path. عند المستوى i، تختار حرفًا من digits[i] بإلحاقه، ثم تستكشف كل ما تحته باستدعاء تكراري على i+1، ثم تتراجع عن الاختيار بإزالة الحرف. هذا التراجع هو ما يتيح لمخزن مؤقت واحد خدمة الشجرة كلها: بعد حفظ ad وae وaf، تعيد عملية الحذف path إلى a، ثم إلى السلسلة الفارغة، لتكون جاهزة لـ b. عندما يساوي i طول digits، يكون المخزن المؤقت إجابة كاملة، فتحفظ نسخة منه.

إن تجربة الحروف من اليسار إلى اليمين عند كل مستوى تزور الأوراق بالترتيب القاموسي، لذا لا يحتاج الناتج إلى فرز. في هذه المسألة، ينتهي كل فرع بإجابة، لذا لا يوجد ما ينبغي تقليمه؛ فعمق الشجرة لا يتجاوز 4 مستويات، ولها 256 ورقة على الأكثر. يظل العمل O(4^n · n) لكتابة الإجابات، لكن الذاكرة الإضافية تقتصر على المخزن المؤقت ومكدس الاستدعاءات، O(n)، بدلًا من مستوى كامل من البادئات. وتحل الحلقة نفسها، التي تختار وتستكشف وتتراجع، مسائل المجموعات الجزئية والتبديلات ومجموع التركيبات والبحث عن الكلمات.

الخوارزمية

احتفظ بمسار path فارغًا وبنتيجة result فارغة.
عرّف backtrack(i): إذا كان i يساوي طول digits، فاحفظ نسخة من path ثم أعد القيمة.
وإلا، فلكل حرف على مفتاح digits[i]، بالترتيب: أضِفه إلى path، واستدعِ backtrack(i+1)، ثم أزِله.
استدعِ backtrack(0) وأعِد result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

أخطاء شائعة وحالات حدّية

البحث نفسه قصير، لذا تأتي معظم الأخطاء من لوحة المفاتيح أو من المخزن المؤقت المشترك.

افتراض أن لكل مفتاح ثلاثة أحرف. يحتوي المفتاح 7 على pqrs والمفتاح 9 على wxyz، لذا فإن أخذ ثلاثة أحرف بدءًا من الفهرس (d-2)*3 من الأبجدية يحذف الحرف s من 7 ويجعل 8 يبدأ بالحرف s بدلًا من t. اكتب لوحة المفاتيح في جدول.
نسيان التراجع. من دون إزالة الحرف بعد الاستدعاء العودي، يستمر path في النمو، وتكون الإجابة الثانية عن "23" هي ade بدلًا من ae.
حفظ المخزن المؤقت بدلًا من نسخة منه. في Python، يخزّن result.append(path) القائمة نفسها تسع مرات، وبحلول النهاية تكون فارغة. حوّلها إلى سلسلة نصية جديدة عند حفظها.
فقدان الترتيب. تؤدي تجربة أحرف المفتاح من اليمين إلى اليسار، أو إنشاء السلاسل من مكدس في النسخة التكرارية، إلى ظهور الإجابات بترتيب مختلف عن الترتيب المصنف الذي تطلبه المسألة.
قراءة سلسلة الأرقام كعدد. في اللغات ذات الأنواع المرنة مثل PHP وR، قد تصلك "23" على هيئة العدد 23. حوّلها إلى نص قبل فهرسة أحرفها.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة تركيبات أحرف رقم الهاتف؟

إنه O(4^n · n) بالنسبة إلى n من الأرقام: يمكن أن يكون هناك 4^n سلسلة، عندما يكون كل رقم 7 أو 9، وتستغرق كتابة كل منها n خطوة. ومع المفاتيح ذات الأحرف الثلاثة فقط، يكون التعقيد O(3^n · n). لا يمكن لأي حل أن يكون أفضل، لأن هذا هو حجم المخرجات. يحتاج التراجع إلى مساحة إضافية O(n) إلى جانب المخرجات.

هل يمكنك حل Letter Combinations دون استخدام الاستدعاء الذاتي؟

نعم. كوِّن الإجابات مستوىً تلو الآخر: ابدأ بسلسلة فارغة واحدة، ولكل رقم، أضف كل حرف من أحرف ذلك المفتاح إلى كل سلسلة لديك. ينفّذ ذلك المقدار نفسه من العمل، ويجتاز الشجرة نفسها بعرضها أولًا بدلًا من التعمق أولًا. يحتفظ بمستوى كامل من البادئات في الذاكرة، بينما لا تحتاج الاستدعاءات العودية إلا إلى مكدس بعمق يساوي عدد الأرقام.

لماذا تُرجع خوارزمية التراجع التركيبات بترتيب مُرتَّب؟

جميع الإجابات لها الطول نفسه، وتنتهي عملية المرور بعمق أولًا من كل سلسلة تبدأ بـ a قبل أن تختار b في المستوى الأول. وينطبق الأمر نفسه على كل مستوى، ما دامت أحرف كل مفتاح تُجرَّب من اليسار إلى اليمين. وهذا هو ترتيب القاموس تمامًا، لذا لا حاجة إلى الفرز.

ماذا عن الرقمين 0 و1؟

على لوحة مفاتيح الهاتف، لا يقابل الرقمين 0 و1 أي أحرف، وهذا الإصدار من المسألة يستخدم الأرقام من 2 إلى 9 فقط. لو كان من الممكن ظهورهما، لكان عليك أن تقرر ما إذا كان ينبغي تخطي هذا الرقم أم أن ذلك يجعل الإجابة فارغة، إذ لا يتيح أي حرف للاختيار منه. في مقابلة، اسأل أي الخيارين مطلوب قبل كتابة الكود.

Python

def letterCombinations(digits):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

digits = "23"

المتوقع

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]