কনটেন্টে যান

018 — Word Break

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

  • Original source: Classic cross-topic capstone interview problem (string segmentation family)
  • Platform: LeetCode — https://leetcode.com/problems/word-break/
  • 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।

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

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

তোমাকে একটা string s আর কিছু শব্দের একটা dictionary দেওয়া আছে। তোমার কাজ: বলো s-কে dictionary-র শব্দ দিয়ে পুরোপুরি ভাগ করা (segment) যায় কিনা — মানে এক বা একাধিক dictionary-word পরপর জুড়ে ঠিক s বানানো যায় কিনা। প্রতিটা শব্দ যতবার খুশি ব্যবহার করা যায়। শুধু True/False চাই।

উদাহরণ
s : "leetcode",  dict : ["leet", "code"]
"leet" + "code"  -> পুরো s ঢেকে যায়  -> True

Input ও output

উদাহরণ
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

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

ভাবো তোমাকে স্পেস-বিহীন একটা লম্বা লেখা দেওয়া হলো, আর একটা শব্দকোষ। তুমি বাঁ দিক থেকে এগোচ্ছ আর প্রতিটা থামার জায়গায় একটা পেন্সিল-দাগ দিচ্ছ মানে "এ পর্যন্ত পুরোটা বৈধ শব্দে ভাঙা গেছে"। নতুন একটা জায়গায় দাগ দিতে পারবে তখনই, যদি আগের কোনো দাগ থেকে এই জায়গা পর্যন্ত টুকরোটা শব্দকোষে থাকে। শেষ পর্যন্ত দাগ পৌঁছালে — পুরো লেখাটাই ভাঙা গেছে।

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

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

এই 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)।

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

লুকানো logic একটা prefix reachability: dp[i] সত্য তখনই, যখন কোনো একটা split-পয়েন্ট j < i আছে যেখানে — (ক) প্রথম j character আগে থেকেই segment করা যায় (dp[j] সত্য), আর (খ) মাঝের টুকরো s[j:i] একটা dictionary-word। সূত্রে —

উদাহরণ
dp[i] = True  যদি কোনো j থাকে (0 <= j < i) যাতে  dp[j] AND s[j:i] in words

dp[0] = True (খালি prefix সবসময় segment করা যায় — base)। শেষে dp[n]-ই পুরো string-এর উত্তর।

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

দুটো জিনিস — একটা boolean array dp length n + 1 (prefix-reachability, 12 DP), আর dictionary থেকে বানানো একটা set words (O(1) lookup, 05 hashing)। substring slice 02 strings-এর কাজ।

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

প্রতিটা 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 নিখুঁত ফিট।

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

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

প্রথম সরল চিন্তা: একটা recursion — solve(start) মানে "start index থেকে বাকি string segment করা যায় কি"। প্রতিটা সম্ভাব্য prefix s[start:end] যদি শব্দ হয়, তাহলে বাকিটা solve(end) recurse করো।

উদাহরণ
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

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

memo ছাড়া এই recursion একই start index বারবার নতুন করে গণনা করে — খারাপ ক্ষেত্রে call tree exponential, প্রায় O(2^n) (যেমন "aaaa...a" with ["a","aa",...])। একই suffix বহু আলাদা prefix-পথ দিয়ে ফিরে আসে। এই পুনরাবৃত্তিই 12 DP দূর করে — প্রতিটা index-এর উত্তর একবার গুনে cache করে।

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

মূল observation: পুরো string segment করা যায় কিনা তা শুধু "কোন কোন prefix segment করা যায়" তার উপর নির্ভর করে — অতীতে ঠিক কোন শব্দ-ভাঙা ব্যবহার হয়েছে তা মনে রাখার দরকার নেই, শুধু "এ পর্যন্ত পৌঁছানো গেছে কিনা" (boolean) জানলেই চলে। এই observation exponential branching-টাকে n-টা স্বাধীন prefix-প্রশ্নে নামায়, প্রতিটা O(n) কাজে — মোট O(n^2)।

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

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

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

মোচড়: "পুরো string কীভাবে ভাঙব" ভাবার বদলে ভাবো "প্রতিটা থামার জায়গা পর্যন্ত পৌঁছানো যায় কি?" — একটা prefix-এর উত্তর শুধু আগের কোনো reachable prefix + একটা শব্দ-টুকরোর উপর দাঁড়ায়। বিশাল recursive branching গলে যায় একটা সরল বাঁ-থেকে-ডান boolean fill-এ।

ছবিতে বোঝা

s = "leetcode", words = {"leet", "code"}। dp[i] = প্রথম i char segment করা যায়?

উদাহরণ
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-এ ধাপে ধাপে

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।

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

Python

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

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

  • 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 মিলিয়ে দেখা

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

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

সময়

O(n^2 × L) — বাইরের loop n বার, ভেতরের split-loop O(n) বার, প্রতিবার substring slice + set-lookup O(L) (L = গড় substring দৈর্ঘ্য)। সাধারণত O(n^2) হিসেবে ধরা হয় (slice-cost ছোট ধরে)।

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

O(n + W) — boolean dp array O(n), আর dictionary set-এ মোট অক্ষর O(W)। recursion+memo করলেও একই, শুধু call-stack O(n) যোগ হতো।

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

  • 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-এর সাথে মেলে।

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

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

ভিত্তি: prefix-reachability boolean DP (12 DP-র ../../12-dynamic-programming/patterns.md, prefix family) + dictionary-কে set-এ রেখে O(1) lookup (05 hashing-এর ../../05-hashing/) + substring slice (02 strings-এর ../../02-arrays-and-strings/)। এই তিনটে cold অবস্থায় জানা থাকলে segmentation DP নিজে থেকেই দাঁড়িয়ে যায়।

পরের অনুশীলন

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

Prefix DP + set lookup (segmentation): dp[i] = প্রথম i char ভাঙা যায় কিনা; dp[i] = OR over j of (dp[j] AND s[j:i] in set)। dictionary set-এ রেখে lookup O(1), prefix boolean reuse করে O(n^2)। DP + hashing + strings combo-র canonical রূপ।

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

ভবিষ্যতের আমাকে: "string-টা dictionary দিয়ে ভাঙা যায় কি" দেখলেই prefix DP মনে করবে — dictionary আগে set-এ ঢালো, dp[0]=True, প্রতিটা i-তে আগের reachable j + শব্দ-টুকরো খোঁজো। dictionary list রেখে দিও না (lookup ধীর হয়), আর dp[0]=True base ভুলো না। DP-prefix, set-lookup আর string-slice-এর সবচেয়ে পরিষ্কার মেলবন্ধন।

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