016 — Word Break

Source

• Original source: Classic string-segmentation DP exercise
• Platform: LeetCode — https://leetcode.com/problems/word-break/
• Topic: dynamic programming
• Difficulty: Medium
• Pattern: 1D over string prefixes
• Basic idea inherited from: Hashing (folder 05) দ্রুত word-lookup-এর জন্য, আর #2 Climbing Stairs-এর "শেষ ধাপ কোথা থেকে?" prefix-চিন্তা

1. Problem in simple words

একটা string s আর একটা শব্দ-তালিকা (dictionary) wordDict দেওয়া। প্রশ্ন: s-কে কি dictionary-র এক বা একাধিক শব্দে (space দিয়ে) পুরোপুরি কাটা যায়? প্রতিটা শব্দ যত খুশি বার ব্যবহার করা যায়। শুধু "হ্যাঁ/না" (boolean) বলতে হবে।

s = "leetcode", wordDict = ["leet", "code"]
"leet" + "code" -> পুরোটা ঢাকা পড়ে -> True

s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
কোনো বিভাজনই পুরো string ঢাকে না (শেষে "og" আটকে যায়) -> False

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) হতো।

6. Real-life analogy

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

7. Visual explanation

dp[i] = s[0:i] segmentable কি না (T/F)। s = "leetcode", words = {leet, code}:

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<i of ( dp[j] AND s[j:i] in words )

dp[0] = True                      (base: খালি prefix)
dp[4]: j=0 -> dp[0]=T এবং s[0:4]="leet" in words -> True
dp[8]: j=4 -> dp[4]=T এবং s[4:8]="code" in words -> True   <- answer

(dp[1..3], dp[5..7] কোনো valid break পায় না -> False)

প্রতিটা position-এ সব আগের break-point দেখি; একটাও "আগে-সবুজ + মাঝের-টুকরো-শব্দ" হলে এই position সবুজ। উত্তর dp[n]।

8. Example input and output

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)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা শুরু-বিন্দু থেকে recurse করা — প্রথম শব্দটা কতদূর, ঠিক করে বাকি অংশ একইভাবে সমাধান।

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:

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 সমাধান।

14. Step-by-step dry run

s = "cars", words = {car, ca, rs}, tabulation:

1. dp = [T, F, F, F, F] (dp[0]=T)
2. i=1: j=0 → dp[0]=T, s[0:1]="c" in words? না → dp[1]=F
3. i=2: j=0 → s[0:2]="ca" in words? হ্যাঁ, dp[0]=T → dp[2]=T
4. i=3: j=0 → "car"? হ্যাঁ, dp[0]=T → dp[3]=T (j=2 দেখার দরকার নেই)
5. i=4: j=0 → "cars"? না; j=2 → dp[2]=T, s[2:4]="rs" in words? হ্যাঁ → dp[4]=T
6. return dp[4] = True

হাতে মিলিয়ে: "ca" + "rs" = "cars" ঢেকে যায়। ✔

15. Python solution

# ---- way 1: tabulation (bottom-up), set = hashing ----
def word_break_tab(s, word_dict):
    words = set(word_dict)                    # O(1) lookup
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                              # খালি prefix
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:     # আগে-সবুজ + মাঝের টুকরো শব্দ
                dp[i] = True
                break
    return dp[n]

# ---- way 2: memoization (top-down) ----
def word_break_memo(s, word_dict):
    words = set(word_dict)
    n = len(s)
    memo = {}
    def can(start):                           # s[start:] segmentable?
        if start == n:
            return True
        if start in memo:
            return memo[start]
        for end in range(start + 1, n + 1):
            if s[start:end] in words and can(end):
                memo[start] = True
                return True
        memo[start] = False
        return False
    return can(0)

# ---- tests ----
cases = [
    ("leetcode", ["leet", "code"], True),
    ("applepenapple", ["apple", "pen"], True),
    ("catsandog", ["cats", "dog", "sand", "and", "cat"], False),
    ("a", ["a"], True),
    ("ab", ["a"], False),
    ("aaaaaaa", ["aaaa", "aaa"], True),
    ("", ["a"], True),                        # খালি string segmentable
    ("cars", ["car", "ca", "rs"], True),
]
for s, wd, want in cases:
    assert word_break_tab(s, wd) == want, (s, word_break_tab(s, wd))
    assert word_break_memo(s, wd) == want, (s, word_break_memo(s, wd))

print("সব test pass!")

16. Line-by-line code explanation

• word_break_tab: dictionary-কে set-এ রাখে (O(1) lookup); dp[0]=True; প্রতিটা prefix-শেষ i-এর জন্য সব break-point j দেখে — dp[j] সত্যি ও s[j:i] শব্দ হলে dp[i]=True করে break; answer dp[n]।
• word_break_memo: can(start) suffix s[start:] segmentable কি না; প্রথম শব্দ s[start:end] শব্দ হলে আর বাকিটা segmentable হলে True; memo repeated কাজ এড়ায়।
• দুই function-ই set-এর উপর নির্ভর করে — এটাই lookup সস্তা রাখে।

17. Output walkthrough

cases-এ আটটা input — LeetCode-এর তিন classic (leetcode, applepenapple True; catsandog False), single-char True/False, repeat-word aaaaaaa True, খালি string edge ("" → True), আর একটা ছোট cars True। প্রতিটার জন্য দুই function-ই মিলতে হবে। সব pass হলে শেষে print: সব test pass!।

18. Time complexity

দুই version-ই O(n²) breakpoint জোড়া, প্রতিটায় substring তৈরি + set lookup (substring slicing O(length) ধরলে worst-case O(n³); set lookup নিজে O(1) average)। (Naive recursion ছিল exponential।)

19. Space complexity

• Tabulation: O(n) — dp array (+ dictionary set)।
• Memoization: O(n) — dict + recursion stack (+ set)।

20. Common mistakes

• dictionary-কে list-এ রেখে lookup করা — তখন প্রতিটা membership-check O(dict size), পুরোটা অনেক ধীর; set-এ রাখো।
• dp[0] = True না বসানো — কোনো prefix-ই সবুজ হয় না, সবসময় False ভুল উত্তর।
• substring সীমা গুলিয়ে ফেলা — শেষ শব্দ s[j:i] (j থেকে i, i বাদ), আর dp[j] আগের অংশ; এই index alignment নিখুঁত হতে হবে।

21. Which basic problem this inherits from

ভিত্তি: Hashing (folder 05) দ্রুত lookup-এর জন্য + #2 Climbing Stairs-এর prefix/last-step চিন্তা, string-এর index-এ তোলা। ../state-transition-thinking.md-এর "Problem 1 — Climbing Stairs"-এর "শেষ move কোথা থেকে?" lens এখানে "শেষ শব্দ কোথা থেকে?"; ../patterns.md-এর "1D over string prefixes" family-ও এখানে।

22. Similar harder problems

• Word Break II (শুধু হ্যাঁ/না নয়, সব বিভাজন বের করো) — https://leetcode.com/problems/word-break-ii/
• Concatenated Words (dictionary-র শব্দ অন্য শব্দ জুড়ে বানানো) — https://leetcode.com/problems/concatenated-words/
• Palindrome Partitioning (একই prefix-DP কঙ্কাল, condition palindrome) — https://leetcode.com/problems/palindrome-partitioning/

23. Pattern learned

1D over string prefixes: state dp[i] = prefix s[0:i]-এর কোনো property (এখানে segmentable), transition সব break-point j < i-এর উপর dp[j] and (s[j:i] valid), base dp[0]=True, answer dp[n]। DP কঙ্কালের পাশে সঠিক data structure (hash set) — দুটো একসাথে efficiency দেয়।

24. Final summary

ভবিষ্যতের আমাকে: "Word Break = prefix-এর উপর 1D boolean DP + hash set lookup।" State dp[i] = s[0:i] segmentable, transition dp[i] = OR_j (dp[j] and s[j:i] in words), base dp[0]=True, উত্তর dp[n]। মনে রেখো: dictionary সবসময় set-এ; "শেষ শব্দ কোথা থেকে শুরু?" — এই last-decision lens-ই চাবি।

25. JavaScript solution (with test cases)

prefix-এর উপর 1D boolean DP + Set lookup; dp[i] = OR_j (dp[j] && s.slice(j,i) in words)।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// dp[i] = prefix s[0:i] segmentable কি না
function wordBreak(s, wordDict) {
  const words = new Set(wordDict);            // O(1) lookup
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;                               // খালি prefix
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {  // আগে-সবুজ + মাঝের টুকরো শব্দ
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}
// ---- test cases (example + edge) ----
const cases = [
  ["leetcode", ["leet", "code"], true],
  ["applepenapple", ["apple", "pen"], true],
  ["catsandog", ["cats", "dog", "sand", "and", "cat"], false],
  ["a", ["a"], true],
  ["ab", ["a"], false],                       // "b" ঢাকা পড়ে না
  ["aaaaaaa", ["aaaa", "aaa"], true],
  ["", ["a"], true],                          // খালি string segmentable
  ["cars", ["car", "ca", "rs"], true],
];
for (const [s, wd, want] of cases) {
  assert(wordBreak(s, wd) === want, "break " + JSON.stringify(s));
}
console.log("সব JS test pass!");

JS টীকা: dictionary-কে Set-এ রাখো — array.includes O(n), Set.has O(1); list-এ রাখলে পুরোটা অনেক ধীর। substring পেতে s.slice(j, i) (i exclusive) — Python-এর s[j:i]-এর সমতুল্য; index alignment নিখুঁত হতে হবে (dp[j] আগের অংশ, s.slice(j,i) শেষ শব্দ)। dp[0] = true base ভুলে গেলে সব false ভুল উত্তর।

26. TypeScript solution (with test cases)

function wordBreak(s: string, wordDict: string[]): boolean {
  const words: Set<string> = new Set(wordDict);
  const n: number = s.length;
  const dp: boolean[] = new Array(n + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
const cases: Array<[string, string[], boolean]> = [
  ["leetcode", ["leet", "code"], true],
  ["applepenapple", ["apple", "pen"], true],
  ["catsandog", ["cats", "dog", "sand", "and", "cat"], false],
  ["a", ["a"], true],
  ["ab", ["a"], false],
  ["", ["a"], true],
  ["cars", ["car", "ca", "rs"], true],
];
for (const [s, wd, want] of cases) expect(wordBreak(s, wd), want, "break");
console.log("সব TS test pass!");

TS টীকা: Set<string> typing দিয়ে dictionary যে string-এর set তা locked, ভুল-type membership-check আটকায়; dp: boolean[] segmentability-flag-এর type স্পষ্ট করে। cases: Array<[string, string[], boolean]> tuple-type প্রতিটা case-এর [s, dict, expected] গঠন নিশ্চিত করে।

27. কোথায় কাজে লাগে (real-world use)

• Tokenization / word segmentation: space-হীন বা compound text (যেমন চীনা/জাপানি, বা URL slug) জানা-শব্দে ভাঙা যায় কিনা।
• Spell-check / input validation: একটা string বৈধ শব্দ-অংশে বিভাজ্য কিনা যাচাই (autocomplete dictionary দিয়ে)।
• DNA / sequence parsing: sequence-কে জানা motif/segment-এ সম্পূর্ণ ভাগ করা সম্ভব কিনা।
• Command / DSL parsing: input-কে জানা token-এ segmentable কিনা পরীক্ষা (lexing feasibility)।
• Compound word detection: একটা শব্দ ছোট জানা-শব্দ জুড়ে তৈরি কিনা।

মূল pattern: prefix-এর উপর 1D DP — "শেষ শব্দ কোথা থেকে শুরু?" last-decision lens; dictionary সবসময় hash Set-এ।

---

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