17. Letter Combinations of a Phone Number حل المسئلة مع الشرح

نص المسئلة

قم بتحويل نص فيه الأرقام من 2 إلى 9 إلى كل الإحتمالات الممكنة للحروف التي يمكن تكوينها ، تُقبل الإجابة بأى ترتيب لهذه الإحتمالات.

شكل ربط الأرقام بالحروف في الصورة كما في الهواتف:

مثال 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

مثال 2:

Input: digits = "2"
Output: ["a","b","c"]

يمكنكم زيارة المسئلة في الموقع الرسمي leetcode من هنا

الحل:

طبعاً أول شئ افكر فيه أني محتاج طريقة لتحويل الرقم إلى الحروف المرتبطة به ويمكن إنجاز ذلك بأكثر من طريقة ولكننا هنا سنستخدم hash map بسيطة كالتالي:

function letterCombinations(digits: string): string[] {
    let keyMaps = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }
};

حسناً نفكر هنا في الحل وهو بسيط فمثلاً إذا كان ال input رقم واحد مثل 2 فإن الناتج سيكون أن نمر على كل حروفه ونضعه في مصفوفة وسيكون الحل عبارة عن :

["a","b","c"]

وإذا كان ال input عبارة عن “23” فلاحظ أنك ستمر على الإجابة الخاصة بالرقم 2 وستقوم بإضافة العنصر الأول من 3 وهو “d” إلى كل عناصر ال 2 ثم نقوم بإضافة العنصر الثاني من الرقم 3 وهو “e” إلى كل عناصر الرقم 2 وهكذا ، وإذا كان ال input ثلاثة أرقام فإنك ستحل حل الرقمين ثم تضيف جميع عناصر الرقم الثالث إلى ناتج حل الرقمين الثانيين.

وهنا نلاحظ أننا أمام مسئلة فيها recursion لأننا نقوم بحل المسئلة عن طريق إضافة حلول إلى الحل السابق والحل السابقة يقوم بإضافة حلول إلى الحل الذي يسبقة وهكذا.

وكيف سنقوم بتحقيق ذلك؟

سنقوم بإنشاء دالة ستسقبل متغييرين أساسين هما p , up :

p اختصار processed وفيه سنقوم بتخزين الناتج من العملية السابقة.

up اختصار unprocessed وفيه سنقوم بتخزين الأرقام المأخوذه من ال input وسنقوم بحذف ما قمنا بإيجاد إجابته مسبقاً كلما قامت الدالة باستدعاء نفسها :

function letterCombinationsRecursive(p: string, up: string, keyMaps: Record<string, string>): string[] {
    
}

لاحظ أننا أيضاً سنستقبل ال keyMap التي قمنا بصناعتها في الدالة الأم.

ثم سنقوم بتنفيذ ما قمنا بشرحه بالأعلى سنقوم حل أول رقم من ال up،

فنقوم أولاً بأخذ أول حرف من ال input :

let firstChar = up.charAt(0)

ثم نقوم بتحويله إلى الحروف المربوطة به من ال keyMap :

let firstCharletters = keyMaps[firstChar]

ثم نقوم بالمرور على كل هذه الحروف وإضافتها للإجابة السابقة (p) ولكن قت تسأل هذه أول دورة ولا يوجد إجابة سابقة أقول لك سنفترض أن الإجابة السابقة “” (نص فارغ) مما سيجعل الحروف تكون هي الإجابة:

وكيف سنقوم بإضافة هذه الحروف إلى مصفوفة كلُ واحد منهم على حده؟ سنقوم بعمل شرط في أول الدالة ونقول للدالة إذا كان ال up فارغ أي أنه لا يوجد حروف أخرى فيجب أن نعود ولكن لن نعود فارغي الأيدي سنقوم بالعودة ومعنا أحد الحلول في مصفوفة خاصة به هو وحده.

if (up.length === 0) {
    return [p]
}

إذاً حتى الآن شكل الدالة:

function letterCombinationsRecursive(p: string, up: string, keyMaps: Record<string, string>): string[] {
    if (up.length === 0) {
        return [p]
    }
    let firstChar = up.charAt(0)
    let firstCharletters = keyMaps[firstChar]
}

حسناً الآن يجب علينا أن نمر على كل الحروف التي لدينا في المتغير firstCharletters وكل حرف نقوم بإضافته إلى الحل السابق p ونستدعي الدالة لنقول لها قومي بحل باقي الحروف في up.

function letterCombinationsRecursive(p: string, up: string, keyMaps: Record<string, string>): string[] {
    if (up.length === 0) {
        return [p]
    }
    let firstChar = up.charAt(0)
    let firstCharletters = keyMaps[firstChar]

    for (let i = 0; i < firstCharletters.length; i++) {
        letterCombinationsRecursive(p + firstCharletters[i], up.substring(1), keyMaps)
    }
}

هنا نقوم باستعداء الدالة وأقول لها أن أحد الحلول عبارة عن الحل السابق مضافة عليه أحد حروف الرقم الحالي p + firstCharletters[i]

ثم أُرسل up.substring(1) وهو باقي الحروف لأنني قمت بحل الحرف الاول وهذه الدالة ستقوم باستقطاع أول حرف من النص وإرسالة مع الدالة لتقوم الدالة بحله.

ولكن هنا مشكلة بعد أن نستدعي الدالة في for loop فإنها ستحسب الناتج ولن تصنع به شئ ونحن نريد أن نخزن هذه النواتج التي ستخرج في مصفوفة وعمل return لها فنقوم بعمل متغير خارج ال loop ونقوم بتخيزن الناتج به ثم عمل return له.

function letterCombinationsRecursive(p: string, up: string, keyMaps: Record<string, string>): string[] {
    if (up.length === 0) {
        return [p]
    }
    let firstChar = up.charAt(0)
    let firstCharletters = keyMaps[firstChar]
    let res = [];
    for (let i = 0; i < firstCharletters.length; i++) {
        res.push(...letterCombinationsRecursive(p + firstCharletters[i], up.substring(1), keyMaps))
    }
    return res;
}

لماذا وضعنا (…) قبل استعداء الدالة ؟ لأن الدالة ال return الخاص بها يكون مصفوفة فيها كل الحلول السابقة فإذا قمنا بعمل push سينتج لدينا مصفوفة بها مصفوفات من الحلول فيجب كل مرة أن نقوم بعمل spread للمصوفة.

وهذا هو الحل النهائي نقوم طبعاً باستدعاء هذه الدالة في الدالة الأم كالتالي:

function letterCombinations(digits: string): string[] {
    let keyMaps = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }
    return letterCombinationsRecursive("", digits, keyMaps)
};

function letterCombinationsRecursive(p: string, up: string, keyMaps: Record<string, string>): string[] {
    if (up.length === 0) {
        return [p]
    }
    let firstChar = up.charAt(0)
    let firstCharletters = keyMaps[firstChar]
    let res = [];
    for (let i = 0; i < firstCharletters.length; i++) {
        res.push(...letterCombinationsRecursive(p + firstCharletters[i], up.substring(1), keyMaps))
    }
    return res;
}

Time Complexity

حيث n هو عدد عناصر ال input.