কনটেন্টে যান

003 — Backspace String Compare

Problem link ও উৎস

  • Original source: Classic stack-simulation exercise
  • Platform: LeetCode — https://leetcode.com/problems/backspace-string-compare/
  • Topic: stack
  • Difficulty: Easy
  • Pattern: stack simulation
  • Basic idea inherited from: matching / undo (problem 1) — # মানে শেষ character undo করা

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

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

তোমাকে দুটো string s আর t দেওয়া আছে, যেন কেউ একটা text editor-এ এগুলো type করেছে। এখানে # মানে backspace — মানে আগের একটা character মুছে দাও। দুটো string টাইপ করা শেষ হলে যে final text পাওয়া যায়, সে দুটো এক হলে True, নাহলে False return করো।

মনে রেখো: খালি text-এ backspace চাপলে কিছুই হয় না (মোছার মতো কিছু নেই)।

Input ও output

উদাহরণ
Input : s="ab#c",  t="ad#c"   -> Output: True    (দুটোই "ac")
Input : s="ab##",  t="c#d#"   -> Output: True    (দুটোই "")
Input : s="a#c",   t="b"      -> Output: False   ("c" vs "b")

Edge case (খালি-stack backspace): s="a##c", t="#a#c" -> True (দুটোই "c")

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

মোবাইলে message টাইপ করা ভাবো। অক্ষর চাপলে শেষে যোগ হয়; backspace চাপলে শেষ অক্ষরটা মুছে যায় — আগেরটা নয়, মাঝেরটা নয়, সবসময় শেষটা। আর input box খালি থাকলে backspace চাপলে কিছুই হয় না। এই "শেষে যোগ, শেষ থেকে মোছা" আচরণটাই stack।

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

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

এটা problem 1 (Valid Parentheses)-এর undo discipline-এর সরাসরি বংশধর। সেখানে closing bracket একটা খোলা context কে "শেষ" করত (pop); এখানে # শেষ typed character-টা "undo" করে (pop)। দুটোতেই key হলো: সবচেয়ে recent জিনিসটাই প্রথমে মুছে যায় — LIFO।

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

লুকানো logic হলো একটা character-এর চূড়ান্ত ভাগ্য তার ডানদিকের #-গুলোর উপর নির্ভর করে। তুমি যদি বাঁ থেকে ডানে process করো, একটা stack-এ চিন্তা সহজ: সাধারণ character push হয়, # সবচেয়ে recent push-টা pop করে। শেষে stack-এ যা থাকে সেটাই আসল text। invariant: যেকোনো মুহূর্তে stack = "এখন পর্যন্ত টাইপ করা, যা এখনো মোছা হয়নি।"

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

প্রতিটা string-এর জন্য একটা stack (Python list)। দুটো string-এর final stack বানিয়ে সরাসরি তুলনা করি।

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

# মানে "শেষ typed character মুছে দাও" — ঠিক stack-এর pop, O(1)। সাধারণ character "শেষে যোগ করো" — append, O(1)। array-র মাঝখানে delete করতে গেলে O(n) shift লাগত; stack ঠিক যে প্রান্তটা দরকার (শেষ) সেটাই cheap রাখে, তাই নিখুঁত fit।

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

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

প্রথম সরল চিন্তা: প্রতিটা # পেলে string-টা আক্ষরিকভাবে কেটে ছোট করি।

উদাহরণ
"ab#c": '#'-এ পৌঁছে আগের char 'b' আর '#' নিজে — দুটোই মুছে -> "ac"
প্রতিবার '#' পেলে string slice করে নতুন বানাও।

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

প্রতিবার #-এ string-টা slice/rebuild করলে প্রতিটা rebuild O(n), আর অনেকগুলো # থাকলে → O(n^2)। stack-ভিত্তিক approach পুরো string-এ একবার হাঁটে, প্রতিটা character-এ O(1) কাজ — মোট O(n)।

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

মূল observation: # সবসময় সবচেয়ে recent টিকে-থাকা character-কে মোছে। "সবচেয়ে recent টিকে-থাকা"-টা ঠিক stack-এর top। তাই একবার বাঁ-থেকে-ডানে scan করে stack maintain করলেই final text বেরিয়ে আসে।

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

প্রতিটা string-এর জন্য একটা helper লেখো যেটা string-এ হাঁটে: সাধারণ character হলে append, # হলে (stack খালি না হলে) pop। helper দুটো string-এর final stack ফেরত দেয়; সেই দুটো list সমান কিনা দেখো।

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

মোচড়: "দুটো string তুলনা করব" — সরাসরি না ভেবে, আগে প্রতিটাকে তার আসল রূপে evaluate করো (backspace গুলো প্রয়োগ করে), তারপর তুলনা করো। evaluation-এর হাতিয়ারই হলো stack।

ছবিতে বোঝা

"ab#c" কীভাবে "ac" হয়, stack দিয়ে দেখি:

উদাহরণ
char   action                       stack (top ডানে)
'a'    normal -> push               [a]
'b'    normal -> push               [a, b]
'#'    backspace -> pop শেষ (b)     [a]
'c'    normal -> push               [a, c]
result = "ac"

খালি stack-এ backspace — "#a#c":

উদাহরণ
'#'    backspace কিন্তু stack খালি -> কিছু হয় না   []
'a'    push                                         [a]
'#'    pop a                                        []
'c'    push                                         [c]
result = "c"

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

Input s="ab##", t="c#d#":

build("ab##"):

  1. 'a' → push → [a]
  2. 'b' → push → [a, b]
  3. '#' → pop → [a]
  4. '#' → pop → [] → result []

build("c#d#"):

  1. 'c' → push → [c]
  2. '#' → pop → []
  3. 'd' → push → [d]
  4. '#' → pop → [] → result []

দুটো result সমান ([] == []) → return True

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

Python

Python
def backspace_compare(s, t):
    def build(string):
        stack = []
        for ch in string:
            if ch == '#':
                if stack:            # খালি না হলেই মোছো
                    stack.pop()
            else:
                stack.append(ch)
        return stack
    return build(s) == build(t)

# ---- tests ----
assert backspace_compare("ab#c", "ad#c") is True    # দুটোই "ac"
assert backspace_compare("ab##", "c#d#") is True     # দুটোই ""
assert backspace_compare("a#c", "b") is False        # "c" vs "b"
assert backspace_compare("a##c", "#a#c") is True     # দুটোই "c"
assert backspace_compare("xywrrmp", "xywrrmu#p") is True
print("সব test pass!")

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

  • def build(string): — একটা string-কে তার final (backspace-প্রয়োগ-করা) রূপে রূপান্তর করে।
  • if ch == '#': — backspace হলে শেষ character মোছার চেষ্টা।
  • if stack: — তবে stack খালি হলে কিছু করা যাবে না (খালি text-এ backspace = no-op)।
  • stack.pop() — সবচেয়ে recent character মুছে ফেলো।
  • else: stack.append(ch) — সাধারণ character শেষে যোগ করো।
  • return build(s) == build(t) — দুটো final list সমান হলেই True।

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

backspace_compare("ab##", "c#d#") → section 14-এর মতো দুটোই খালি [] → True। backspace_compare("a#c", "b") → build("a#c") = ['c'], build("b") = ['b'], সমান নয় → False। সব assert pass হয়ে শেষে print: সব test pass!।

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

সময়

O(n + m) — s-এ n character, t-এ m character; প্রতিটা ঠিক একবার push/pop হয়।

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

O(n + m) — দুটো stack, সবচেয়ে খারাপ ক্ষেত্রে (কোনো # নেই) পুরো string জমে। (চাইলে two-pointer দিয়ে পিছন থেকে scan করে O(1) space-এ নামানো যায় — harder variant।)

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

  • খালি stack-এ pop করা — # পেলে আগে if stack: check না করলে error বা ভুল ফল।
  • backspace-এর সময় শুধু #-টা মুছে আগের character না মোছা (বা উল্টোটা) — দুটোই বাদ যাওয়ার কথা; stack approach-এ একটা pop-ই দুটো সামলায়।
  • দুটো string আলাদা দৈর্ঘ্যের বলে সাথে সাথে False ভাবা — backspace-এর পর final length এক হতে পারে।

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

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

ভিত্তি: problem 1 (Valid Parentheses)-এর undo/pop discipline; chapter-এর ../patterns.md-এর Pattern 1 (Matching / Nesting / Undo)। সেখানে "closing event pop করে", এখানে "# pop করে" — একই কঙ্কাল।

পরের অনুশীলন

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

Stack as a typing buffer: "backspace / undo / শেষ character মুছো" দেখলেই string-টা একটা stack দিয়ে রি-বিল্ড করো, তারপর তুলনা/ব্যবহার করো।

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

ভবিষ্যতের আমাকে: "backspace = pop।" দুটো জিনিস তুলনার আগে যদি প্রতিটাকে আগে 'evaluate' করতে হয়, ভাবো stack দিয়ে রি-বিল্ড করার কথা। খালি-stack backspace যেন no-op হয় — সেই if stack: guard ভুলবে না।

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