Skip to content

003 — Backspace String Compare

Source

  • 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 করা

1. Problem in simple words

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

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

2. Which basic idea does this inherit from?

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

3. What is the hidden math or logic?

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

4. Which data structure is needed?

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

5. Why this data structure fits

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

6. Real-life analogy

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

7. Visual explanation

"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"

8. Example input and 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")

9. Brute force thinking

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

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

10. Why brute force is slow

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

11. Key observation

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

12. Optimized intuition

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

13. Thinking tweak

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

14. Step-by-step dry run

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

15. Python solution

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

16. Line-by-line code explanation

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

17. Output walkthrough

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

18. Time complexity

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

19. Space complexity

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

20. Common mistakes

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

21. Which basic problem this inherits from

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

22. Similar harder problems

23. Pattern learned

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

24. Final summary

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