Word Break Problem in DSA Typescript - Build from Scratch

Word Break Problem

📖 Scenario: Imagine you have a long string of letters without spaces, and you want to check if it can be split into meaningful words from a given list. This is like trying to find spaces in a sentence that someone wrote without pressing the spacebar.

🎯 Goal: You will build a program that checks if a given string can be segmented into a sequence of dictionary words.

📋 What You'll Learn

Create a string variable with a specific sentence without spaces

Create an array of strings representing the dictionary words

Write a function that checks if the string can be segmented into dictionary words

Print the result as true or false

💡 Why This Matters

🌍 Real World

This problem is useful in text processing, like splitting words in languages without spaces or in spell checkers.

💼 Career

Understanding this problem helps in roles involving natural language processing, search engines, and software that processes human language.

1

Create the input string

Create a string variable called inputString and set it to "applepenapple".

DSA Typescript

# Your code here

Hint

Use const to create a string variable named inputString.

2

Create the dictionary array

Create an array of strings called dictionary with these exact words: "apple", "pen".

DSA Typescript

const inputString = "applepenapple";
# Your code here

Hint

Use const to create an array named dictionary with the words inside square brackets.

3

Write the word break function

Write a function called wordBreak that takes inputString and dictionary as parameters and returns true if inputString can be segmented into words from dictionary, otherwise false. Use a loop and recursion or dynamic programming inside the function.

DSA Typescript

const inputString = "applepenapple";
const dictionary = ["apple", "pen"];

# Your code here

Hint

Use a boolean array dp to keep track of valid breaks. Loop through the string and check substrings against the dictionary.

4

Print the result

Use console.log to print the result of calling wordBreak with inputString and dictionary.

DSA Typescript

const inputString = "applepenapple";
const dictionary = ["apple", "pen"];

function wordBreak(s: string, wordDict: string[]): boolean {
    const dp: boolean[] = new 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] && wordDict.includes(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[s.length];
}

# Your code here

Hint

Call console.log(wordBreak(inputString, dictionary)) to see if the string can be segmented.

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