Skip to content

018 — Word Break

Source

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

1. Problem in simple words

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

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

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। সূত্রে —

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

6. Real-life analogy

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

7. Visual explanation

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

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

9. Brute force thinking

প্রথম সরল চিন্তা: একটা 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

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

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।

15. Python solution

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 করা গেল কিনা — সেটাই উত্তর।

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

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

21. Which basic problem this inherits from

ভিত্তি: 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 নিজে থেকেই দাঁড়িয়ে যায়।

22. Similar harder problems

23. Pattern learned

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 রূপ।

24. Final summary

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