Problem link ও উৎস
- **Original source:** Classic cross-topic capstone interview problem (string segmentation family)
- **Platform:** LeetCode —
- **Topic:** dynamic programming + hashing + strings
- **Difficulty:** Medium
- **Pattern:** Prefix DP + set lookup (segmentation feasibility)
- **Basic idea inherited from:** এটা একটা cross-topic capstone — এখানে মেশে **12 dynamic programming** (প্রতিটা prefix segment করা যায় কিনা, তার একটা boolean array), **05 hashing** (dictionary-টা set-এ রেখে O(1) word-lookup), আর **02 strings** (substring slice নিয়ে কাজ)। তিন tool জোড়া লাগলেই prefix DP segmentation।
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা string `s` আর কিছু শব্দের একটা dictionary দেওয়া আছে। তোমার কাজ: বলো `s`-কে dictionary-র শব্দ দিয়ে **পুরোপুরি ভাগ করা (segment)** যায় কিনা — মানে এক বা একাধিক dictionary-word পরপর জুড়ে ঠিক `s` বানানো যায় কিনা। প্রতিটা শব্দ **যতবার খুশি** ব্যবহার করা যায়। শুধু `True`/`False` চাই।
```text
s : "leetcode", dict : ["leet", "code"]
"leet" + "code" -> পুরো s ঢেকে যায় -> True
```
### Input ও output {#8-example-input-and-output}
```text
Input : s="leetcode", dict=["leet","code"] -> Output: True # leet+code
Input : s="applepenapple", dict=["apple","pen"] -> Output: True # apple+pen+apple (reuse)
Input : s="catsandog", dict=["cats","dog","sand","and","cat"] -> Output: False
Edge case 1 (একটাই শব্দ): s="a", dict=["a"] -> Output: True
Edge case 2 (overlap ফাঁদ): s="aaaaaaa", dict=["aaaa","aaa"] -> Output: True # aaaa+aaa
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমাকে স্পেস-বিহীন একটা লম্বা লেখা দেওয়া হলো, আর একটা শব্দকোষ। তুমি বাঁ দিক থেকে এগোচ্ছ আর প্রতিটা থামার জায়গায় একটা পেন্সিল-দাগ দিচ্ছ মানে "এ পর্যন্ত পুরোটা বৈধ শব্দে ভাঙা গেছে"। নতুন একটা জায়গায় দাগ দিতে পারবে তখনই, যদি আগের কোনো দাগ থেকে এই জায়গা পর্যন্ত টুকরোটা শব্দকোষে থাকে। শেষ পর্যন্ত দাগ পৌঁছালে — পুরো লেখাটাই ভাঙা গেছে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
এই problem তিনটে আগের chapter-এর tool জোড়া দেয়:
- **12 dynamic programming** থেকে: `dp[i]` = "`s`-এর প্রথম `i` character segment করা যায় কি" — প্রতিটা prefix-এর জন্য একটা boolean sub-answer রাখা।
- **05 hashing** থেকে: dictionary-টা একটা **set**-এ রেখে দেওয়া, যাতে "এই substring কি একটা শব্দ?" O(1)-এ জানা যায় (list হলে প্রতিবার O(words))।
- **02 strings** থেকে: substring slice `s[j:i]` বের করে সেটা শব্দ কিনা দেখা।
একা DP দেয় prefix-গুলোর উত্তর reuse; একা set দেয় দ্রুত word-lookup; strings দেয় টুকরো কাটা। তিনটে মিললে O(n^2)।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **prefix reachability**: `dp[i]` সত্য তখনই, যখন কোনো একটা split-পয়েন্ট `j < i` আছে যেখানে — (ক) প্রথম `j` character আগে থেকেই segment করা যায় (`dp[j]` সত্য), আর (খ) মাঝের টুকরো `s[j:i]` একটা dictionary-word। সূত্রে —
```text
dp[i] = True যদি কোনো j থাকে (0 <= j < i) যাতে dp[j] AND s[j:i] in words
```
`dp[0] = True` (খালি prefix সবসময় segment করা যায় — base)। শেষে `dp[n]`-ই পুরো string-এর উত্তর।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
দুটো জিনিস — একটা **boolean array `dp`** length `n + 1` (prefix-reachability, 12 DP), আর dictionary থেকে বানানো একটা **set `words`** (O(1) lookup, 05 hashing)। substring slice 02 strings-এর কাজ।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রতিটা split-পয়েন্ট-এ আমরা বারবার জিজ্ঞেস করি "`s[j:i]` কি একটা শব্দ?" — এটা একটা **membership** প্রশ্ন, set-এর জন্মগত কাজ (05 hashing), O(1)। আর prefix-গুলোর "segment করা যায় কি" উত্তর বারবার লাগে (বড় `i`-র জন্য ছোট `j`-গুলো), তাই index-able boolean array-তে রেখে দিলে (12 DP) আর নতুন করে গুনতে হয় না — prefix-গুলো `0..n` পরপর integer, array নিখুঁত ফিট।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: একটা recursion — `solve(start)` মানে "`start` index থেকে বাকি string segment করা যায় কি"। প্রতিটা সম্ভাব্য prefix `s[start:end]` যদি শব্দ হয়, তাহলে বাকিটা `solve(end)` recurse করো।
```text
def solve(start):
if start == n: return True
for end in range(start+1, n+1):
if s[start:end] in words and solve(end):
return True
return False
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
memo ছাড়া এই recursion একই `start` index **বারবার** নতুন করে গণনা করে — খারাপ ক্ষেত্রে call tree exponential, প্রায় **O(2^n)** (যেমন `"aaaa...a"` with `["a","aa",...]`)। একই suffix বহু আলাদা prefix-পথ দিয়ে ফিরে আসে। এই পুনরাবৃত্তিই 12 DP দূর করে — প্রতিটা index-এর উত্তর একবার গুনে cache করে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **পুরো string segment করা যায় কিনা তা শুধু "কোন কোন prefix segment করা যায়" তার উপর নির্ভর করে** — অতীতে ঠিক কোন শব্দ-ভাঙা ব্যবহার হয়েছে তা মনে রাখার দরকার নেই, শুধু "এ পর্যন্ত পৌঁছানো গেছে কিনা" (boolean) জানলেই চলে। এই observation exponential branching-টাকে n-টা স্বাধীন prefix-প্রশ্নে নামায়, প্রতিটা O(n) কাজে — মোট O(n^2)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
dictionary-টা set-এ ঢালো (দ্রুত lookup)। একটা boolean `dp` নাও, `dp[0] = True`। `i = 1` থেকে `n` পর্যন্ত হাঁটো; প্রতিটা `i`-তে সব split-পয়েন্ট `j < i` দেখো — যদি `dp[j]` সত্য আর `s[j:i]` একটা শব্দ, তাহলে `dp[i] = True` করে inner loop ভাঙো (একটা বৈধ ভাঙা পেলেই যথেষ্ট)। শেষে `dp[n]`-ই উত্তর। প্রতিটা `i`-তে O(n) split + O(len) substring — মোট O(n^2)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "পুরো string কীভাবে ভাঙব" ভাবার বদলে ভাবো "প্রতিটা থামার জায়গা পর্যন্ত পৌঁছানো যায় কি?" — একটা prefix-এর উত্তর শুধু আগের কোনো reachable prefix + একটা শব্দ-টুকরোর উপর দাঁড়ায়। বিশাল recursive branching গলে যায় একটা সরল বাঁ-থেকে-ডান boolean fill-এ।
### ছবিতে বোঝা {#7-visual-explanation}
`s = "leetcode"`, `words = {"leet", "code"}`। `dp[i]` = প্রথম `i` char segment করা যায়?
```text
index: 0 1 2 3 4 5 6 7 8
char: l e e t c o d e
dp: T ? ? ? ? ? ? ? ?
i=4: j=0 -> dp[0]=T AND s[0:4]="leet" in words -> dp[4]=T
i=8: j=4 -> dp[4]=T AND s[4:8]="code" in words -> dp[8]=T
(অন্য j-গুলোতে substring শব্দ না, বা dp[j]=F)
dp = [T,F,F,F,T,F,F,F,T] উত্তর dp[8] = True
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`s = "ab"`, `words = {"a", "b"}`:
1. শুরু: `dp = [T, F, F]` (index 0..2)
2. `i=1`: `j=0` → `dp[0]=T` আর `s[0:1]="a" in words` → `dp[1]=True`, break
3. `i=2`: `j=0` → `dp[0]=T` কিন্তু `s[0:2]="ab"` শব্দ না; `j=1` → `dp[1]=T` আর `s[1:2]="b" in words` → `dp[2]=True`, break
4. return `dp[2] = True` (যেমন `"a"+"b"`)
আরেকটা: `s = "ab"`, `words = {"a"}` → `i=2`-তে কোনো split মেলে না (`"ab"` নেই, `"b"` নেই), `dp[2]=False` → return `False`।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
def word_break(s, word_dict):
words = set(word_dict) # 05 hashing: O(1) word-lookup
n = len(s)
dp = [False] * (n + 1) # dp[i] = প্রথম i char segment করা যায়?
dp[0] = True # খালি prefix সবসময় বৈধ (base)
for i in range(1, n + 1):
for j in range(i): # সব split-পয়েন্ট j < i
if dp[j] and s[j:i] in words:
dp[i] = True
break # একটা বৈধ ভাঙা পেলেই যথেষ্ট
return dp[n]
# ---- tests ----
assert word_break("leetcode", ["leet", "code"]) == True
assert word_break("applepenapple", ["apple", "pen"]) == True # reuse "apple"
assert word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]) == False
assert word_break("a", ["a"]) == True
assert word_break("aaaaaaa", ["aaaa", "aaa"]) == True # 4+3
assert word_break("ab", ["a"]) == False # "b" ঢাকা পড়ে না
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `words = set(word_dict)` — list-কে set-এ বদলানো, যাতে membership-চেক O(1) (05 hashing)।
- `dp = [False] * (n + 1)` — সব prefix শুরুতে "segment করা যায় না"।
- `dp[0] = True` — খালি prefix (০ character) সবসময় বৈধ; পুরো DP-র base।
- `for i in range(1, n + 1)` — প্রতিটা prefix-দৈর্ঘ্য `i` ছোট থেকে বড় (12 DP fill order)।
- `for j in range(i)` — `i`-র আগের প্রতিটা সম্ভাব্য split-পয়েন্ট।
- `if dp[j] and s[j:i] in words` — প্রথম `j` char বৈধ আর মাঝের টুকরো একটা শব্দ? (02 strings slice + 05 set lookup)।
- `dp[i] = True; break` — পেলে `i`-prefix বৈধ, আর খোঁজার দরকার নেই।
- `return dp[n]` — পুরো string segment করা গেল কিনা — সেটাই উত্তর।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`"leetcode"`-এ `dp[4]` ("leet") আর তারপর `dp[8]` ("code") True হয়ে যায় — return True, assert pass। `"applepenapple"`-এ "apple" দুবার ব্যবহার হয়ে (set-এ থাকায় পুনর্ব্যবহার free) `dp[13]` True। `"catsandog"`-এ `dp` কখনো শেষ পর্যন্ত পৌঁছায় না (`"og"`/`"dog"`-এর আগে valid prefix মেলে না), return False। `"ab"` with `["a"]`-এ `dp[2]` False। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n^2 × L)** — বাইরের loop n বার, ভেতরের split-loop O(n) বার, প্রতিবার substring slice + set-lookup O(L) (L = গড় substring দৈর্ঘ্য)। সাধারণত O(n^2) হিসেবে ধরা হয় (slice-cost ছোট ধরে)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n + W)** — boolean `dp` array O(n), আর dictionary set-এ মোট অক্ষর O(W)। recursion+memo করলেও একই, শুধু call-stack O(n) যোগ হতো।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- dictionary list রেখে দেওয়া (set না বানানো) — তখন প্রতিটা lookup O(words), মোট ধীর; set-এ ঢালো।
- `dp[0] = True` সেট না করা — base ছাড়া কোনো prefix-ই কখনো True হবে না, সবসময় False।
- inner loop-এ `break` ভুলে যাওয়া (সঠিকতা নষ্ট হয় না, কিন্তু একটু ধীর) — একটা ভাঙা পেলেই থামা ভালো।
- substring index ভুল করা — `s[j:i]` মানে index `j` থেকে `i-1` পর্যন্ত; `i` exclusive, এটাই প্রথম `i` char-এর সাথে মেলে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: prefix-reachability boolean DP (12 DP-র [../../12-dynamic-programming/patterns.md](../../12-dynamic-programming/patterns.md), prefix family) + dictionary-কে set-এ রেখে O(1) lookup (05 hashing-এর [../../05-hashing/](../../05-hashing/README.md)) + substring slice (02 strings-এর [../../02-arrays-and-strings/](../../02-arrays-and-strings/README.md))। এই তিনটে cold অবস্থায় জানা থাকলে segmentation DP নিজে থেকেই দাঁড়িয়ে যায়।
### পরের অনুশীলন {#22-similar-harder-problems}
- Word Break II (শুধু True/False না, **সব** বৈধ ভাঙা ফেরত দাও — DP + backtracking) —