Problem link ও উৎস
- **Original source:** Classic hash map mapping exercise
- **Platform:** LeetCode —
- **Topic:** hash map
- **Difficulty:** Easy
- **Pattern:** grouping / mapping
- **Basic idea inherited from:** two synchronized dicts — দুটো dict একসাথে রেখে দুই-দিকের consistency রক্ষা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
দুটো string `s` আর `t` দেওয়া আছে। বলো — এরা কি **isomorphic**? অর্থাৎ `s`-এর প্রতিটা অক্ষরকে কি এমন একটা নির্দিষ্ট অক্ষরে বদলে `t` বানানো যায়, যেখানে (১) একই অক্ষর সবসময় একই অক্ষরে যায়, আর (২) দুটো ভিন্ন অক্ষর কখনো একই অক্ষরে গিয়ে মেশে না?
```text
s = "egg", t = "add" → True (e→a, g→d, ধারাবাহিক)
s = "foo", t = "bar" → False (o-কে একবার a, একবার r বানাতে হতো)
```
### Input ও output {#8-example-input-and-output}
```text
Input : s = "egg", t = "add" Output: True
Input : s = "foo", t = "bar" Output: False
Input : s = "paper", t = "title" Output: True
Edge : s = "badc", t = "baba" Output: False (d আর c দুটোই b/a-তে মেশে)
Edge : s = "", t = "" Output: True (দুটোই খালি)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা গোপন সংকেতলিপি (cipher), যেখানে প্রতিটা অক্ষর আরেকটা নির্দিষ্ট অক্ষরে বদলায় — A সবসময় হয় Q, B সবসময় হয় Z। নিয়ম দুটো: একই অক্ষর সবসময় একই বদলি পায়, আর দুটো ভিন্ন অক্ষর কখনো একই বদলি ভাগ করে না (নইলে decode করার সময় গুলিয়ে যাবে)। তোমার দুটো codebook — একটা encode-এর, একটা decode-এর — সবসময় মিলতে হবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এটা দাঁড়িয়ে আছে **two synchronized dicts**-এর উপর — mapping/grouping (Pattern 3)-এর একটা রূপ। একটা dict রাখে `s`-এর অক্ষর → `t`-এর অক্ষর, আরেকটা রাখে উল্টোটা (`t` → `s`)। দুটো একসাথে রক্ষা করলে নিশ্চিত হয় mapping টা **bijection** (one-to-one, দুই দিকেই সঙ্গতিপূর্ণ)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **bijection** (এক-এক মিল)। শুধু `s → t` map রাখলে "একই অক্ষর একই জায়গায় যায়" শর্তটা ধরা পড়ে, কিন্তু "দুটো অক্ষর এক জায়গায় মেশে না" শর্তটা ফসকে যায়। তাই উল্টো `t → s` map-ও লাগে। দুই map সবসময় সঙ্গতিপূর্ণ থাকলেই isomorphic — একটা invariant যা প্রতি অক্ষরে রক্ষা করতে হয়।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো **hash map** (`dict`): `s_to_t` (`s`-এর অক্ষর → `t`-এর অক্ষর) আর `t_to_s` (উল্টোটা)। দুটো একসাথে দুই-দিকের mapping ধরে রাখে।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা অক্ষরের mapping mনে রাখা আর "এই অক্ষর আগে অন্য কিছুতে map হয়েছিল কি?" — এই lookup গড়ে **O(1)**। তাই string জুড়ে একবার হেঁটেই consistency যাচাই হয়ে যায়। dict এই "key → তার নির্দিষ্ট partner" সম্পর্ক ধরে রাখার জন্য একদম তৈরি।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা অক্ষরের জন্য মনে মনে ভেবে দেখি আগে কোথাও আলাদা mapping হয়েছিল কি না — অর্থাৎ প্রতিবার পুরো ইতিহাস ঘেঁটে দেখা।
```text
প্রতিটা position i-র জন্য:
s[i] কি আগে অন্য কোনো t-অক্ষরে map হয়েছিল? (পেছনের সব position খুঁজি)
t[i] কি আগে অন্য কোনো s-অক্ষরে এসেছিল? (আবার খুঁজি)
গরমিল পেলে → return False
return True
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা position-এ আগের সব position আবার ঘাঁটা = মোট **O(n^2)**। অথচ mapping দুটো dict-এ জমিয়ে রাখলে "আগে কোথায় map হয়েছিল" প্রশ্নের উত্তর O(1)-এ পাওয়া যায়। বারবার ইতিহাস scan করাই অপচয়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: isomorphic হতে হলে mapping টা **দুই-দিকেই** এক-এক হতে হবে। তাই দুটো dict — `s→t` আর `t→s` — একসাথে রক্ষা করলে দুটো শর্তই (consistency + কোনো merge নয়) এক পাসে ধরা পড়ে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
`s` আর `t`-কে position-ধরে জোড়ায় জোড়ায় (`zip`) হাঁটো। প্রতিটা জোড়া `(a, b)`-তে দেখো: `a` আগে map হয়ে থাকলে সেটা কি `b`-তেই? আর `b` আগে এসে থাকলে সেটা কি `a` থেকেই? দুটোর কোনোটা না মিললে `False`। মিললে দুই dict-এ mapping টা রেখে এগোও। পুরো string শেষ হলে `True`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** এক-দিকের map যথেষ্ট মনে হলেও আসলে নয় — "দুটো অক্ষর এক জায়গায় মেশা" ঠেকাতে উল্টো map-ও লাগে। দুটো synchronized dict রাখলেই bijection-এর দুই শর্ত একসাথে রক্ষা পায়।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "egg"`, `t = "add"`। দুটো map গড়তে গড়তে এগোই:
```text
জোড়া (e,a): e নতুন, a নতুন → s_to_t={e:a}, t_to_s={a:e}
জোড়া (g,d): g নতুন, d নতুন → s_to_t={e:a, g:d}, t_to_s={a:e, d:g}
জোড়া (g,d): e→? না, g→d আছে, d→g আছে, সঙ্গতিপূর্ণ → ঠিক আছে
সব মিলল → return True
```
আর conflict হলে (`s="foo"`, `t="bar"`):
```text
(f,b): নতুন → s_to_t={f:b}, t_to_s={b:f}
(o,a): নতুন → s_to_t={f:b, o:a}, t_to_s={b:f, a:o}
(o,r): o আগে a-তে map হয়েছিল, এখন r চাইছে → conflict → return False
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `s = "foo"`, `t = "bar"`:
1. length: `3 == 3` → এগোও; `s_to_t = {}`, `t_to_s = {}`।
2. জোড়া `(f, b)`: কেউ আগে নেই → `s_to_t = {f:b}`, `t_to_s = {b:f}`।
3. জোড়া `(o, a)`: কেউ আগে নেই → `s_to_t = {f:b, o:a}`, `t_to_s = {b:f, a:o}`।
4. জোড়া `(o, r)`: `o` আগে `a`-তে map হয়েছিল, এখন চাইছে `r` (`a != r`) → return `False`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def is_isomorphic(s, t):
if len(s) != len(t):
return False
s_to_t = {}
t_to_s = {}
for a, b in zip(s, t):
if a in s_to_t and s_to_t[a] != b: # s-অক্ষর আগে অন্যত্র map হয়েছিল?
return False
if b in t_to_s and t_to_s[b] != a: # t-অক্ষর আগে অন্য কেউ দখল করেছিল?
return False
s_to_t[a] = b
t_to_s[b] = a
return True
# ---- tests ----
assert is_isomorphic("egg", "add") == True
assert is_isomorphic("foo", "bar") == False
assert is_isomorphic("paper", "title") == True
assert is_isomorphic("badc", "baba") == False
assert is_isomorphic("", "") == True
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `if len(s) != len(t): return False` — আলাদা দৈর্ঘ্যে position-wise mapping সম্ভবই নয়।
- `s_to_t`, `t_to_s` — দুই-দিকের codebook; একটা `s→t`, একটা `t→s`।
- `for a, b in zip(s, t)` — একই position-এর অক্ষর-জোড়া একসাথে নিই।
- `if a in s_to_t and s_to_t[a] != b` — `a` আগে map হয়ে থাকলে সেটা কি এখনকার `b`-র সাথে মেলে? না মিললে consistency ভাঙল।
- `if b in t_to_s and t_to_s[b] != a` — `b` আগে অন্য কোনো অক্ষর দখল করেছিল কি? করলে দুই অক্ষর এক জায়গায় মিশছে — নিষিদ্ধ।
- `s_to_t[a] = b` / `t_to_s[b] = a` — দুই dict-এ mapping টা রেখে দাও।
- `return True` — পুরো string জুড়ে কোনো conflict না হলে isomorphic।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"egg","add"`: e↔a, g↔d ধারাবাহিক → `True`। `"foo","bar"`: দ্বিতীয় `o` আগের `a`-mapping ভাঙে → `False`। `"paper","title"`: p↔t, a↔i, e↔l, r↔e সব এক-এক → `True`। `"badc","baba"`: `d`-কে `b`-তে map করতে গেলে `b` আগেই `b`-র দখলে — conflict → `False`। দুই খালি string → loop চলে না → `True`। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n)** — string-এর উপর একবার হাঁটি, প্রতি অক্ষরে dict operation গড়ে O(1)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(k)** — `k` = distinct অক্ষরের সংখ্যা, দুই dict-এ জমে (alphabet সীমিত হলে কার্যত O(1))।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- শুধু এক dict (`s→t`) রাখা — তখন `"badc"/"baba"`-র মতো case ধরা পড়ে না, কারণ দুটো ভিন্ন `s`-অক্ষর একই `t`-অক্ষরে মেশা ঠেকানো যায় না।
- length check বাদ দেওয়া — `zip` ছোট string-এ থেমে যায়, তাই বড়টার বাকি অংশ পরীক্ষাই হয় না।
- consistency check-এর **আগে** mapping লিখে ফেলা — তখন এই-position-এর mapping দিয়েই নিজেকে যাচাই করে ভুল pass দেয়; আগে check, পরে লেখো।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: mapping/grouping (Pattern 3) — তবে এখানে canonical key নয়, two synchronized dicts দিয়ে bijection রক্ষা। [../patterns.md](../patterns.md)-র Pattern 3 আর [../operations.md](../operations.md)-র dict-mapping অংশ দেখো।
### পরের অনুশীলন {#22-similar-harder-problems}
- Word Pattern —