008 — Letter Combinations of a Phone Number¶

Source¶

Original source: Classic backtracking exercise (phone keypad)
Platform: LeetCode — https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Topic: recursion / backtracking (Cartesian choose-explore)
Difficulty: Medium
Pattern: Cartesian choose-explore — প্রতি digit-এ k-way branch
Basic idea inherited from: Subsets branching, k-way

1. Problem in simple words¶

পুরোনো phone keypad-এ প্রতিটা digit-এর সাথে কিছু অক্ষর থাকে: 2 → abc, 3 → def, ... 9 → wxyz। "23"-এর মতো একটা digit-string দেওয়া আছে। তোমার কাজ: প্রতিটা digit থেকে একটা করে অক্ষর নিয়ে গড়া সব সম্ভাব্য word বের করা। "23"-এ প্রথম digit থেকে a/b/c, দ্বিতীয় থেকে d/e/f — মোট 3×3 = 9টা word।

"23" -> "ad","ae","af","bd","be","bf","cd","ce","cf"   (3 × 3 = 9)

2. Which basic idea does this inherit from?¶

ভিত্তি হলো Subsets branching, k-way। Subsets-এ প্রতিটা item-এ ঠিক 2টা branch (include/exclude) ছিল। এখানে প্রতিটা digit-এ branch-এর সংখ্যা = ওই digit-এর অক্ষরসংখ্যা (3 বা 4)। অর্থাৎ fixed-2 branching-এর বদলে k-way branching — কিন্তু কঙ্কালটা একই choose → explore → un-choose।

3. What is the hidden math or logic?¶

লুকানো math হলো Cartesian product: digit-গুলোর অক্ষর-সেটের সব সম্ভাব্য সংমিশ্রণ। "23" মানে {a,b,c} × {d,e,f}। মোট word-সংখ্যা = প্রতিটা digit-এর অক্ষরসংখ্যার গুণফল (rule of product)। প্রতিটা leaf-এ ঠিক digit-সংখ্যার সমান লম্বা একটা word তৈরি হয়।

4. Which data structure is needed?¶

একটা dict (hash map) digit → অক্ষর mapping রাখতে; একটা list path (বর্তমান word গড়তে); একটা list out (সব word জমাতে); আর recursion-এর জন্য call stack। mapping lookup O(1) বলে dict নিখুঁত।

5. Why this data structure fits¶

dict দিয়ে digits[i] → তার অক্ষরগুলো O(1)-তে পাওয়া যায়, তাই প্রতি level-এ branching options সঙ্গে সঙ্গে হাতে আসে — এটাই hash-map lookup pattern। আর path একটা mutable list বলে append/pop O(1), পুরো decision-tree জুড়ে একটাই word-buffer reuse করা যায়; leaf-এ "".join(path) দিয়ে snapshot বানাই।

6. Real-life analogy¶

একটা combination lock-এর কথা ভাবো যেখানে প্রতিটা চাকতিতে আলাদা সংখ্যক অক্ষর। প্রথম চাকতিতে একটা অক্ষর বাছো, তারপর দ্বিতীয়টায় প্রতিটা অক্ষর ঘুরিয়ে দেখো, তারপর তৃতীয়টায়... প্রথম চাকতির প্রতিটা পছন্দের জন্য বাকি চাকতির সব সংমিশ্রণ ঘোরে। সব চাকতির সব সমন্বয়ই হলো সম্ভাব্য সব word।

7. Visual explanation¶

প্রতি digit-এ k-way branch; leaf-এ পূর্ণ word। "23"-এর decision tree:

                       go(0, "")
            a /          b |          \ c        (digit '2' -> a,b,c)
        go(1,"a")     go(1,"b")     go(1,"c")
        / | \          / | \          / | \      (digit '3' -> d,e,f)
       d  e  f        d  e  f        d  e  f
       |  |  |        |  |  |        |  |  |
      ad ae af       bd be bf       cd ce cf

leaf (index == len(digits)) = 3 × 3 = 9টা word।

8. Example input and output¶

Input : "23" -> Output: ad,ae,af,bd,be,bf,cd,ce,cf   (9টা)
Input : "2"  -> Output: a, b, c

Edge case 1 (খালি): ""  -> Output: []   (কোনো word নেই)
Edge case 2 (4-অক্ষর digit): "9" -> Output: w, x, y, z

9. Brute force thinking¶

প্রথম সরল চিন্তা: nested loop — যত digit তত loop, প্রতিটা loop ওই digit-এর অক্ষরের উপর; ভেতরের সব loop মিলে word গড়ো।

for c1 in letters[d1]:
    for c2 in letters[d2]:
        ... (digit যত, loop তত)
            out.append(c1 + c2 + ...)

10. Why brute force is slow¶

সময়ের দিক থেকে nested loop-ও O(k^L · L)-ই (k = অক্ষর/ digit, L = digit-সংখ্যা) — output-ই তো অত। আসল সমস্যা: loop-সংখ্যা আগে থেকে জানা নেই, কারণ digit-string-এর দৈর্ঘ্য variable। তুমি 2টা digit-এর জন্য 2টা loop, 3টার জন্য 3টা — হাতে লেখা অসম্ভব। recursion ঠিক এই "অজানা গভীরতার nested loop"-টাই সুন্দরভাবে সামলায়।

11. Key observation¶

মূল observation: এটা একটা variable-depth nested loop, আর প্রতি level = এক digit-এর অক্ষরের উপর একটা loop। "সব word কী কী?" না ভেবে ভাবো "এই একটা digit-এর জন্য আমার option কী?" — locally কয়েকটা অক্ষর, recursion বাকি digit-গুলোর সব সমন্বয় খুলে দেয়।

12. Optimized intuition¶

index i ধরে হাঁটো। base case: i == len(digits) হলে path-কে join করে out-এ record করো। নাহলে digits[i]-এর প্রতিটা অক্ষরের উপর loop: অক্ষরটা append (choose), go(i+1) (explore), pop (un-choose)। প্রথমেই digits খালি হলে [] return — guard। এটাই k-way Cartesian backtracking, subsets-এর সরাসরি বড় রূপ।

13. Thinking tweak¶

মোচড়: "কতগুলো nested loop লাগবে?" নিয়ে আটকে না থেকে ভাবো "প্রতি digit-এ একটা loop, আর গভীরতা recursion সামলাবে।" Subsets-এর 2-way branch-কে শুধু k-way বানিয়ে দাও — কঙ্কাল হুবহু এক, শুধু branch-এর সংখ্যা বদলায়।

14. Step-by-step dry run¶

letter_combinations("23"), go(i, path):

go(0,[]), digit '2'→abc। choose a: path=['a'], go(1,['a'])।
go(1,['a']), digit '3'→def। choose d: record "ad", pop; e: record "ae", pop; f: record "af", pop।
ফিরে pop a; choose b: একইভাবে bd, be, bf।
ফিরে pop b; choose c: cd, ce, cf।
out = ["ad","ae","af","bd","be","bf","cd","ce","cf"] — 9টা।

15. Python solution¶

def letter_combinations(digits):
    if not digits:                 # খালি input -> কোনো word নেই
        return []
    mapping = {
        "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
    }
    out = []
    def go(i, path):
        if i == len(digits):       # base case: সব digit-এ অক্ষর বাছা শেষ
            out.append("".join(path))
            return
        for ch in mapping[digits[i]]:
            path.append(ch)        # CHOOSE
            go(i + 1, path)        # EXPLORE
            path.pop()             # UN-CHOOSE
    go(0, [])
    return out

# ---- tests (order-independent তুলনা) ----
assert sorted(letter_combinations("23")) == sorted(
    ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"])
assert sorted(letter_combinations("2")) == ["a", "b", "c"]
assert letter_combinations("") == []                 # খালি input
assert sorted(letter_combinations("9")) == ["w", "x", "y", "z"]  # 4-অক্ষর
assert len(letter_combinations("234")) == 27         # 3 × 3 × 3
assert len(letter_combinations("79")) == 16          # 4 × 4
print("সব test pass!")

16. Line-by-line code explanation¶

if not digits: return [] — খালি string-এ কোনো word নেই; guard আগে।
mapping = {...} — digit → অক্ষর dict, O(1) lookup।
if i == len(digits): — base case: সব digit-এ একটা করে অক্ষর বাছা শেষ।
out.append("".join(path)) — path-এর অক্ষরগুলো জুড়ে একটা word snapshot record।
for ch in mapping[digits[i]]: — এই digit-এর প্রতিটা অক্ষরে k-way branch।
path.append(ch) / go(i+1, path) / path.pop() — choose → explore → un-choose।

17. Output walkthrough¶

letter_combinations("23"): digit 2-এর a,b,c-এর প্রতিটার নিচে digit 3-এর d,e,f বসে — 9টা word (ad…cf)। order নির্ধারিত হলেও sorted দিয়ে তুলনা করায় assert robust। "2"→3টা, ""→[], "9"→w,x,y,z (4টা), "234"→27, "79"→16। সব মিলে print: সব test pass!।

18. Time complexity¶

O(k^L · L) — k = প্রতি digit-এর অক্ষর (3 বা 4), L = digit-সংখ্যা; k^L word, প্রতিটা join করতে L।

19. Space complexity¶

Output বাদ দিলে O(L) — path ও call stack-এর গভীরতা L। Output ধরলে O(k^L · L)।

20. Common mistakes¶

খালি digits-এ []-এর বদলে [""] ফেরত দেওয়া — base case ভুলভাবে চালু হয়; শুরুতেই guard দাও।
path.pop() ভুলে যাওয়া — পরের branch-এ আগের অক্ষর leak করে।
record-এ path (list) রাখা, "".join(path) (string snapshot) না নেওয়া — সব entry একই live list হয়ে যায়।
mapping-এ digit 0/1 ধরে নেওয়া — এদের কোনো অক্ষর নেই; input সাধারণত 2-9।

21. Which basic problem this inherits from¶

ভিত্তি: Subsets (এই tracker-এর #7)-এর include/exclude branching, এখানে k-way রূপে। ../patterns.md-এর Pattern 4-এ এটাকে "digit প্রতি choose, used-set লাগে না" বলা আছে; ../concept.md-এর "ab"-word example দেখো — হুবহু একই কঙ্কাল।

22. Similar harder problems¶

Combinations — https://leetcode.com/problems/combinations/ (এই tracker-এর #11)
Generate Parentheses — https://leetcode.com/problems/generate-parentheses/ (#15)
Combination Sum — https://leetcode.com/problems/combination-sum/ (#12)

23. Pattern learned¶

k-way Cartesian backtracking: প্রতি position-এ ওই position-এর সব option-এর উপর loop চালিয়ে choose → explore → un-choose; variable-depth nested loop-কে recursion দিয়ে সামলানো — Cartesian product enumerate করার মূল pattern।

24. Final summary¶

ভবিষ্যতের আমাকে: "Phone letters = প্রতি digit-এ তার অক্ষরের উপর loop, choose/explore/un-choose; খালি input আগে guard করো।" যখনই 'কয়েকটা set থেকে একটা করে নিয়ে সব সমন্বয়' বা 'অজানা-গভীরতার nested loop' দরকার — এই k-way Cartesian backtracking মনে করবে।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।