কনটেন্টে যান

003 — Reverse String

Problem link ও উৎস

  • Original source: Classic recursion exercise
  • Platform: LeetCode — https://leetcode.com/problems/reverse-string/
  • Topic: recursion (decrease-and-conquer, two ends)
  • Difficulty: Easy
  • Pattern: decrease-and-conquer — swap বাইরের জোড়া, ভেতরের দিকে recurse
  • Basic idea inherited from: swap + ভেতরের দিকে recurse

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

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

একটা character-এর list s দেওয়া আছে (যেমন ["h","e","l","l","o"])। তোমার কাজ: এটাকে in-place উল্টে দেওয়া — মানে নতুন list না বানিয়ে, একই list-এর ভেতরেই character-গুলো অদলবদল করা। শেষে first ও last জায়গা বদলাবে, দ্বিতীয় ও দ্বিতীয়-শেষ বদলাবে, এভাবে মাঝখান পর্যন্ত।

উদাহরণ
আগে : ['h', 'e', 'l', 'l', 'o']
পরে : ['o', 'l', 'l', 'e', 'h']

Input ও output

উদাহরণ
Input : ['h','e','l','l','o'] -> Output: ['o','l','l','e','h']
Input : ['H','a','n','n','a','h'] -> Output: ['h','a','n','n','a','H']

Edge case 1 (খালি): []      -> Output: []
Edge case 2 (একটা char): ['z'] -> Output: ['z']

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

একসারি বই তাকের দুই প্রান্তে দাঁড়িয়ে দুজন মানুষ ভাবো। তারা হাতের বইটা একে অপরের সাথে বদলায়, তারপর দুজনেই এক কদম ভেতরের দিকে এগোয়, আবার বদলায়। মাঝখানে এসে যখন তারা মুখোমুখি (বা পাশাপাশি), তখন পুরো সারি উল্টে গেছে — কেউ বাইরে কোনো অতিরিক্ত তাক ব্যবহার করেনি।

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

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

ভিত্তি হলো swap + ভেতরের দিকে recurse। তুমি যদি জানো কীভাবে দুটো প্রান্তের element অদলবদল করতে হয়, তাহলে পুরো reverse just সেই swap-টা করে এক ধাপ ভেতরে ঢুকে আবার সেই একই কাজ করা। প্রতিটা recursive call problem-টাকে দুই দিক থেকে ছোট করে — এটাই decrease-and-conquer-এর "two ends" রূপ।

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

লুকানো logic একটা invariant: বাইরের দিকের সব জোড়া ইতিমধ্যে ঠিক জায়গায় বসে গেছে, আর left ও right-এর মাঝের অংশটুকু এখনো উল্টানো বাকি। প্রতিটা swap একটা জোড়া fix করে, তারপর left+1, right-1 দিয়ে recurse করায় বাকি অংশ এক ধাপ ছোট হয়। left >= right হলে আর কিছু উল্টানোর নেই।

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

কোনো extra data structure লাগে না — input list (array) নিজেই যথেষ্ট। শুধু দুটো index pointer (left, right) আর recursion-এর জন্য call stack। In-place হওয়ায় এটাই সৌন্দর্য।

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

List-এ index দিয়ে যেকোনো position O(1)-তে read/write করা যায়, তাই দুই প্রান্তের character swap করা মুহূর্তের কাজ। array-র এই random access-ই in-place swap সম্ভব করে — linked list হলে শেষ element-এ পৌঁছাতেই O(n) লাগত। তাই এখানে array নিখুঁতভাবে খাপ খায়।

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

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

প্রথম সরল চিন্তা: একটা নতুন list বানাও আর input-কে শেষ থেকে শুরুর দিকে পড়ে তাতে ঢালো।

উদাহরণ
out = []
for i = len(s)-1 down to 0:
    out.append(s[i])
return out

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

কাজ করে, কিন্তু এটা O(n) extra space নেয় (নতুন list)। অথচ problem চায় in-place, O(1) extra space। তাছাড়া নতুন list বানিয়ে পুরোনোটা বদলানো অপ্রয়োজনীয় — দুই প্রান্তের swap দিয়েই কাজ হয়ে যায়, বাড়তি memory ছাড়াই।

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

মূল observation: পুরো string একসাথে উল্টানোর দরকার নেই — শুধু symmetric জোড়াগুলো (i আর n-1-i) swap করলেই হয়, আর তা করতে হবে শুধু মাঝখান পর্যন্ত। বাকি অর্ধেক swap-গুলো প্রথম অর্ধেকের পুনরাবৃত্তি হবে, তাই left >= right-এ থামাই যথেষ্ট।

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

দুটো index নাও — left = 0, right = n-1। ওদের swap করো, তারপর left+1, right-1 দিয়ে recurse করো। যতক্ষণ left < right, ততক্ষণ একটা করে জোড়া fix হচ্ছে; left >= right হলে base case — থামো। চাইলে loop দিয়েও একই কাজ O(1) space-এ হয়, কিন্তু recursive version-টা decrease-and-conquer-এর "দুই প্রান্ত থেকে ছোট করা" রূপটা সুন্দরভাবে দেখায়।

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

মোচড়: "string উল্টাব" ভাবার বদলে ভাবো "বাইরের জোড়াটা swap করব, তারপর ভেতরের ছোট string-টা উল্টানোর দায়িত্ব recursion-কে দিয়ে দেব।" বড় কাজটা একটা swap + একটা ছোট, একই ধরনের কাজে ভেঙে যায় — leap of faith।

ছবিতে বোঝা

left ও right ভেতরের দিকে এগোয়, প্রতি step-এ একটা swap। ['a','b','c','d']:

উদাহরণ
call helper(0, 3):  ['a','b','c','d']   swap a,d -> ['d','b','c','a']
  └ call helper(1, 2): ['d','b','c','a'] swap b,c -> ['d','c','b','a']
      └ call helper(2, 1): left >= right -> base case, কিছু করো না, return

recursion ফিরে আসে, list এখন: ['d','c','b','a']
গভীরতা ≈ n/2 (প্রতি call দুটো প্রান্ত fix করে)

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

Input ['c','a','t','s'], helper(left, right):

  1. helper(0, 3): left=0 < right=3 → swap s[0],s[3] → ['s','a','t','c']; recurse helper(1,2)।
  2. helper(1, 2): left=1 < right=2 → swap s[1],s[2] → ['s','t','a','c']; recurse helper(2,1)।
  3. helper(2, 1): left=2 >= right=1 → base case, কিছু করো না, return।
  4. recursion unwind করে; final list = ['s','t','a','c']।

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

Python

Python
def reverse_string(s):
    def helper(left, right):
        if left >= right:          # base case: জোড়া শেষ
            return
        s[left], s[right] = s[right], s[left]   # বাইরের জোড়া swap
        helper(left + 1, right - 1)             # ভেতরের দিকে recurse
    helper(0, len(s) - 1)
    return s                       # in-place, তবু সুবিধার জন্য return

# ---- tests ----
assert reverse_string(["h", "e", "l", "l", "o"]) == ["o", "l", "l", "e", "h"]
assert reverse_string(["H", "a", "n", "n", "a", "h"]) == ["h", "a", "n", "n", "a", "H"]
assert reverse_string([]) == []          # খালি list
assert reverse_string(["z"]) == ["z"]    # একটা char

# in-place হচ্ছে কি না যাচাই (একই object বদলাচ্ছে)
arr = ["c", "a", "t", "s"]
reverse_string(arr)
assert arr == ["s", "t", "a", "c"]
print("সব test pass!")

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

  • def helper(left, right) — দুই প্রান্তের index নিয়ে কাজ করা ভেতরের recursive function।
  • if left >= right: return — base case: দুই pointer মিলে গেলে বা পেরিয়ে গেলে আর swap-এর কিছু নেই।
  • s[left], s[right] = s[right], s[left] — Python tuple-swap; বাইরের জোড়া এক লাইনে অদলবদল।
  • helper(left + 1, right - 1) — দুই দিক থেকে এক ঘর ভেতরে; problem ছোট হলো।
  • helper(0, len(s) - 1) — পুরো range দিয়ে শুরু।
  • return s — in-place বদলালেও test-এর সুবিধার জন্য list-টা ফেরত।

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

reverse_string(["h","e","l","l","o"]): helper(0,4) swap h,o; helper(1,3) swap e,l; helper(2,2) base case → ["o","l","l","e","h"]। palindrome-জাতীয় Hannah শুধু H↔h বদলায়। খালি ও single-char case base case-এ সরাসরি থামে। শেষ block প্রমাণ করে একই arr object in-place বদলেছে, তারপর print: সব test pass!।

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

সময়

O(n) — প্রায় n/2 swap, প্রতিটা O(1); মোট linear।

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

O(n) recursion stack-এর জন্য (গভীরতা n/2)। Loop দিয়ে লিখলে O(1); in-place হওয়ায় কোনো নতুন list বানে না।

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

  • base case left >= right-এর বদলে left == right লেখা — জোড় length-এ pointer পরস্পরকে cross করে যায়, তখন থামে না বা ভুল swap হয়।
  • in-place না করে নতুন list return করা — problem-এর শর্ত ভাঙে।
  • left+1, right-1 ভুলে left, right-1 বা উল্টোটা করা — infinite recursion বা ভুল ফল।
  • Python-এ গভীর recursion (খুব বড় list) — depth limit; তখন loop version বেছে নাও।

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

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

ভিত্তি: দুটো element swap + two-pointer ভেতরের দিকে হাঁটা। ../concept.md-এর "Decrease-and-conquer: string reverse" snippet (rev(s[1:]) + s[0]) দেখো — সেটা one-end shrink, এই note two-end swap, একই pattern-এর দুটো রূপ।

পরের অনুশীলন

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

Two-end decrease-and-conquer: বাইরের জোড়া swap করো, তারপর left+1, right-1 দিয়ে ভেতরের ছোট অংশের দায়িত্ব recursion-কে দাও — in-place reversal/palindrome-জাতীয় কাজের মূল pattern।

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

ভবিষ্যতের আমাকে: "Reverse = বাইরের জোড়া swap করে ভেতরের দিকে recurse, left >= right-এ থামো।" যখনই কোনো problem-এ দুই প্রান্ত থেকে কাজ করে মাঝখানে মিলিয়ে দিতে হয় (reverse, palindrome check) — এই two-pointer / two-end pattern মনে করবে।

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