Word Break Problem in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Word Break Problem?

It is a problem where you check if a given string can be split into a sequence of one or more dictionary words.

beginner

What data structure is commonly used to store the dictionary in the Word Break Problem?

A set or hash set is commonly used for fast lookup of dictionary words.

intermediate

What is the main approach to solve the Word Break Problem efficiently?

Use dynamic programming to check substrings and store results to avoid repeated work.

intermediate

In the dynamic programming solution, what does the boolean array represent?

Each position in the array shows if the substring up to that position can be segmented into dictionary words.

beginner

Why is the Word Break Problem important in real life?

It helps in text processing tasks like spell checking, word segmentation in languages without spaces, and autocomplete.

What does the Word Break Problem ask you to determine?

A If a string contains only vowels

B If a string is a palindrome

C If a string can be split into dictionary words

D If a string is sorted alphabetically

The problem checks if the string can be segmented into valid dictionary words.

Which technique is best suited to solve the Word Break Problem efficiently?

A Dynamic Programming

B Greedy Algorithm

C Depth First Search without memoization

D Sorting

Dynamic Programming avoids repeated checks by storing intermediate results.

What does the boolean array in the DP solution represent?

A If substring up to index can be segmented

B If substring is a palindrome

C If substring contains digits

D If substring is empty

Each boolean value shows if the substring up to that index can be formed by dictionary words.

Which data structure is commonly used to store dictionary words for quick lookup?

A Linked List

B Set or HashSet

C Stack

D Queue

Sets provide O(1) average time complexity for lookups.

If the input string is empty, what should the Word Break Problem return?

A False

B Null

C Error

D True

An empty string can be considered segmented trivially.

Explain how dynamic programming helps solve the Word Break Problem.

Think about how you remember which parts of the string can be segmented.

Describe the role of the dictionary in the Word Break Problem and how it is used.

The dictionary is like a word list you trust.

Practice

1. What does the Word Break Problem ask you to determine about a given string s and a dictionary of words wordDict?

easy

A. If s can be reversed to form a word in wordDict

B. If s contains any substring that is not in wordDict

C. If s is exactly equal to one of the words in wordDict

D. If s can be segmented into a space-separated sequence of one or more dictionary words

Solution

1. Step 1: Understand the problem goal

   The Word Break Problem asks if the entire string s can be split into parts where each part is a word from the dictionary wordDict.

2. Step 2: Clarify what is being checked

   It is not about substrings not in the dictionary or exact matches only, but about segmenting s fully into dictionary words.

3. Final Answer:

   If s can be segmented into a sequence of dictionary words -> Option D

4. Quick Check:

   Word Break = segment string into dictionary words [OK]

Hint: Check if string splits fully into dictionary words [OK]

Common Mistakes:

• Thinking it checks for partial substrings only
• Confusing exact match with segmentation
• Assuming reversed words are considered

2. Which of the following TypeScript function signatures correctly represents a function solving the Word Break Problem?

easy

A. function wordBreak(words: string[], s: string): number

B. function wordBreak(s: string, wordDict: string[]): boolean

C. function wordBreak(s: number, wordDict: string): string

D. function wordBreak(s: string, wordDict: string): void

Solution

1. Step 1: Identify correct parameter types

   The function should take a string s and an array of strings wordDict representing the dictionary words.

2. Step 2: Identify correct return type

   The function returns a boolean indicating if s can be segmented or not.

3. Final Answer:

   function wordBreak(s: string, wordDict: string[]): boolean -> Option B

4. Quick Check:

   Correct params and boolean return [OK]

Hint: Function takes string and string array, returns boolean [OK]

Common Mistakes:

• Using wrong parameter types
• Returning wrong data type
• Swapping parameter order

3. What will be the output of the following TypeScript code?

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const dp = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

console.log(wordBreak("leetcode", ["leet", "code"]));

medium

A. SyntaxError

B. false

C. true

D. undefined

Solution

1. Step 1: Understand the dynamic programming approach

   The code uses a boolean array dp where dp[i] is true if substring s[0..i-1] can be segmented into dictionary words.

2. Step 2: Trace the example input "leetcode"

   "leet" and "code" are in the dictionary. The code finds "leet" at start and sets dp[4] true, then "code" from index 4 to 8 sets dp[8] true. So final dp[s.length] is true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   DP finds full segmentation = true [OK]

Hint: Check dp array for full string length true [OK]

Common Mistakes:

• Confusing substring indices
• Not breaking inner loop after true
• Misunderstanding dp array meaning

4. Identify the bug in this TypeScript code for the Word Break Problem:

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  const dp = Array(s.length).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

medium

A. dp array size is incorrect; should be s.length + 1

B. wordSet should be an array, not a Set

C. The substring indices are reversed in s.substring(j, i)

D. dp[0] should be false initially

Solution

1. Step 1: Check dp array initialization

   The dp array is created with size s.length, but it needs to be s.length + 1 to include the base case dp[0].

2. Step 2: Understand consequences of wrong dp size

   Accessing dp[s.length] will be out of bounds, causing runtime errors or incorrect results.

3. Final Answer:

   dp array size is incorrect; should be s.length + 1 -> Option A

4. Quick Check:

   dp size must cover 0 to s.length indices [OK]

Hint: dp array length = string length + 1 [OK]

Common Mistakes:

• Using dp array of wrong size
• Confusing Set with array for dictionary
• Incorrect substring index order

5. Given the string s = "applepenapplepenapple" and dictionary wordDict = ["apple", "pen"], what is the minimum number of segments needed to fully segment s into dictionary words?

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Break down the string into dictionary words

   The string is "applepenapplepenapple". The dictionary words are "apple" and "pen". The string can be segmented as "apple" + "pen" + "apple" + "pen" + "apple".

2. Step 2: Count the segments

   There are 5 segments total: apple, pen, apple, pen, apple.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Count dictionary words in segmentation = 5 [OK]

Hint: Count dictionary words in full segmentation [OK]

Common Mistakes:

• Counting characters instead of words
• Missing repeated segments
• Assuming fewer segments possible