কনটেন্টে যান

008 — Letter Combinations of a Phone Number

Problem link ও উৎস

  • 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

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

পুরোনো 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)

Input ও 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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

ভিত্তি হলো 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।

ভেতরের যুক্তি

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

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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 বানাই।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

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

উদাহরণ
for c1 in letters[d1]:
    for c2 in letters[d2]:
        ... (digit যত, loop তত)
            out.append(c1 + c2 + ...)

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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-এর সরাসরি বড় রূপ।

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

প্রতি 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।

ছোট input-এ ধাপে ধাপে

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

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

কোড ও ব্যাখ্যা

Python

Python
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!")

কোডের প্রতিটি অংশ

  • 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।

Output মিলিয়ে দেখা

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!।

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

  • খালি 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।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।