Letter Combinations of a Phone Number

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

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

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

+10

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

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

الدالة

letterCombinations(digits: string) → string-array

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

القيود

1 ≤ digits.length ≤ 4
كل حرف في digits هو رقم من 2 إلى 9.
تحتوي الإجابة على ما لا يزيد عن 4⁴ = 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.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

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

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

الفكرة

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

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

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

الخوارزمية

ابدأ بـ combos = [""]، أي ببادئة فارغة واحدة.
لكل رقم، أنشئ قائمة جديدة: لكل بادئة في combos، ولكل حرف على مفتاح ذلك الرقم، أضف prefix + letter.
استبدل 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، ولكلٍّ منها أبناء هم d وe وf.

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

يظل الزمن 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

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

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

أسئلة شائعة3

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

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

لماذا يُرجع التراجع التركيبات بترتيب مُرتَّب؟

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

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

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

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

اختبار #1

اختبار #2

اختبار #3

وسيط

digits = "23"

الإخراج المتوقع

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