Leetcode 17. Letter Combinations of a Phone Number

2-9 sonlaridan tashkil topgan string berilgan. Raqamlar ketma-ketligi bo’yicha barcha harf-kombinatsiyalarni array ko’rinishida qaytaring. Sonlarning harflar bo’yicha mappingi quyidagi rasmda keltirilgan. 1 soni hech qanday harfga bog’lanmagan.

Misol:

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

Ishlash tartibi

Yuqorida keltirilgan misolga e’tibor bersangiz, u odatiy tree ma’lumotlar tuzilmasiga o’xshaydi:

Demak bir yechim – berilgan matn raqamlaridan mapping asosida tree yasab olishimiz va tree’ning barglaridagi qiymatlarni array’ga terib chiqishimiz mumkin.

Lekin map asosida ishlaydigan backtracking algoritmli yechim ham bor. Biz quyida uni ko’rib o’tamiz.

1. Telefon harflarini map arrayga yig’ib olamiz:

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

2. digits matnining har bir harfini (raqamini) rekursiv funksiya ichida map ichidan topamiz. Masalan, digits = 56 bo’lsa, const str = map[digits[0]] dan keyin str konstanta 'jkl' qiymatga ega bo’ladi.

3. str matnning har bir harfini alohida prefix array’ga yig’amiz.

4. rekursiv funksiyaga index + 1 argument berib, uni ishga tushiramiz.

5. rekursiv funksiya ichida agar index === digits.length bo’lsa, prefix array’ni stringga o’girib, results arrayga qo’shamiz va funksiyani to’xtatamiz.

6. results arrayni asosiy funksiyaning natijasi sifatida qaytaramiz.

Tushunarli bo’lishi uchun kodni o’rganib chiqqaningiz ma’qul.

Kod