Problem link ও উৎস
- **Original source:** Classic string-segmentation DP exercise
- **Platform:** LeetCode —
- **Topic:** dynamic programming
- **Difficulty:** Medium
- **Pattern:** 1D over string prefixes
- **Basic idea inherited from:** Hashing (folder 05) দ্রুত word-lookup-এর জন্য, আর #2 Climbing Stairs-এর "শেষ ধাপ কোথা থেকে?" prefix-চিন্তা
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা string `s` আর একটা শব্দ-তালিকা (dictionary) `wordDict` দেওয়া। প্রশ্ন: `s`-কে কি dictionary-র এক বা একাধিক শব্দে (space দিয়ে) **পুরোপুরি কাটা যায়**? প্রতিটা শব্দ যত খুশি বার ব্যবহার করা যায়। শুধু "হ্যাঁ/না" (boolean) বলতে হবে।
```text
s = "leetcode", wordDict = ["leet", "code"]
"leet" + "code" -> পুরোটা ঢাকা পড়ে -> True
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
কোনো বিভাজনই পুরো string ঢাকে না (শেষে "og" আটকে যায়) -> False
```
### Input ও output {#8-example-input-and-output}
```text
Input : "leetcode", ["leet","code"] -> True
Input : "applepenapple", ["apple","pen"] -> True (apple+pen+apple)
Input : "catsandog", ["cats","dog","sand","and","cat"] -> False
Edge case 1: "a", ["a"] -> True
Edge case 2: "ab", ["a"] -> False ("b" ঢাকা পড়ে না)
Edge case 3: "", ["a"] -> True (খালি string trivially segmentable)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো একটা space-হীন লম্বা শব্দ, আর তুমি জানা-শব্দের অভিধান দিয়ে সেটায় space বসাতে চাও। বাঁ-থেকে পড়তে পড়তে প্রতিটা position-এ ভাবো: "এই বিন্দু পর্যন্ত কি বৈধভাবে শব্দে কাটা গেছে?" — সেটা সত্যি তখনই, যখন কোনো আগের কাটা-বিন্দু থেকে এই বিন্দু পর্যন্ত অংশটা একটা চেনা শব্দ। একটা চেনা শব্দ পেলেই এই বিন্দু "সবুজ" হয়ে যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত্তি। (১) **Hashing (folder 05):** dictionary-কে একটা `set`-এ রাখি, যাতে "এই substring কি একটা শব্দ?" O(1)-এ যাচাই হয়। (২) **#2 Climbing Stairs-এর prefix-চিন্তা:** সেখানে "step `i`-তে পৌঁছানোর শেষ move কোথা থেকে?" জিজ্ঞেস করতাম; এখানে "prefix `s[0:i]`-এর শেষ শব্দটা কোথায় শুরু?" — string-এর index-গুলোর উপর একটা 1D DP।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: prefix `s[0:i]` segmentable হবে তখনই, যখন এমন একটা break-point `j` (`0 ≤ j < i`) আছে যেখানে — (ক) ছোট prefix `s[0:j]` ইতিমধ্যে segmentable, এবং (খ) মাঝের টুকরো `s[j:i]` dictionary-র একটা শব্দ। মানে শেষ শব্দটা `s[j:i]`, তার আগের সবটুকু আগেই বৈধভাবে কাটা। যেকোনো একটা valid `j` পেলেই `s[0:i]` segmentable।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **1D boolean array** `dp` (size `n + 1`), `dp[i]` = prefix `s[0:i]` (প্রথম `i` অক্ষর) segmentable কি না। সাথে একটা **hash set** `words` দ্রুত lookup-এর জন্য। Top-down করলে dict (`start` → bool)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
State একটামাত্র সংখ্যা: কত-অক্ষর-লম্বা prefix বিবেচনা করছি। তাই prefix-length-কে index ধরা flat boolean array নিখুঁত — `dp[i]` ঠিক `s[0:i]`-এর উত্তর ধরে। dictionary-lookup অসংখ্য বার হয়, তাই list-এর বদলে `set` (hashing) — O(1) membership, যা না হলে প্রতিটা check O(dict size) হতো।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা শুরু-বিন্দু থেকে recurse করা — প্রথম শব্দটা কতদূর, ঠিক করে বাকি অংশ একইভাবে সমাধান।
```text
can(start): # s[start:] কি segmentable?
if start == n: return True # পুরোটা শেষ
for end in start+1 .. n:
if s[start:end] in words and can(end):
return True
return False
answer = can(0)
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
Memoization ছাড়া এই recursion **exponential** — প্রতিটা `start` থেকে অনেকগুলো `end` শাখা, আর একই `start` বহু পথ দিয়ে বারবার পৌঁছানো হয় (overlapping subproblems)। যেমন `"aaaa...a"`-তে break-point combination বিস্ফোরিত হয়। লম্বা string-এ সম্পূর্ণ অসম্ভব।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **distinct state মাত্র `n + 1`-টা** (প্রতিটা prefix-length, বা প্রতিটা start-index)। প্রতিটার উত্তর একবার গুনে রাখলে exponential কাজ O(n²) (× substring/lookup খরচ) হয়ে যায়। আর `set` lookup O(1) বলে substring-যাচাই সস্তা।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
**State (শব্দে):** `dp[i]` = prefix `s[0:i]` (প্রথম `i` অক্ষর) dictionary-র শব্দে পুরোপুরি কাটা যায় কি না (boolean)। (Top-down-এ: `can(start)` = suffix `s[start:]` segmentable কি না।)
**Transition:**
```text
dp[i] = OR over all j in 0..i-1 of ( dp[j] and s[j:i] in words )
```
কারণ: শেষ শব্দ `s[j:i]` — তার আগের prefix `s[0:j]` আগেই বৈধভাবে কাটা থাকতে হবে (`dp[j]`), আর মাঝের টুকরো শব্দ হতে হবে।
**Base case:** `dp[0] = True` (খালি prefix সবসময় segmentable — কিছুই কাটার নেই)।
**Answer location:** `dp[n]` (পুরো string)।
Memoization (top-down): উপরের `can(start)` recursion, dict যোগ। Tabulation (bottom-up): `i = 1..n` বাঁ-থেকে-ডান, প্রতিটায় সব break-point `j < i` দেখো; একটা valid পেলেই `True` দিয়ে break। dictionary সবসময় `set`-এ রাখো।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "সব সম্ভব বিভাজন বের করব" — এই বিশাল search না ভেবে শুধু **শেষ শব্দ** কোথায় শুরু, তা ঠিক করো; বাকিটা ছোট একই problem। আর performance-এর চাবি hashing: dictionary `list`-এ রাখলে প্রতিটা lookup ধীর হয়ে পুরোটা O(n² × m) হয়ে যায়; `set`-এ রাখলে lookup O(1)। DP কঙ্কাল + সঠিক data structure — দুটো মিলেই efficient সমাধান।
### ছবিতে বোঝা {#7-visual-explanation}
`dp[i]` = `s[0:i]` segmentable কি না (T/F)। `s = "leetcode"`, words = {leet, code}:
```text
index : 0 1 2 3 4 5 6 7 8
s : l e e t c o d e
dp : T F F F T F F F T
dp[i] = OR over j