Word Break Problem in DSA Typescript - Time & Space Complexity

Time Complexity: Word Break Problem

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to solve the Word Break Problem changes as the input grows.

Specifically, how does checking if a string can be split into dictionary words scale with string length?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if the string can be split into words from the dictionary using dynamic programming.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where for each position in the string, we check all previous positions.
• How many times: Outer loop runs n times (string length), inner loop runs up to n times, so roughly n x n checks.

How Execution Grows With Input

As the string length grows, the number of checks grows roughly with the square of the length.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: Doubling the string length roughly quadruples the work.

Final Time Complexity

Time Complexity: O(n^3)

This means the time grows roughly with the cube of the string length due to substring extraction and dictionary lookups.

Common Mistake

[X] Wrong: "The solution runs in linear time because it just loops through the string once."

[OK] Correct: There is a nested loop inside, so for each character, it checks all previous positions, making it slower than linear.

Interview Connect

Understanding this time complexity helps you explain your approach clearly and shows you know how nested loops affect performance.

Self-Check

"What if we used a Trie to check dictionary words instead of substring checks? How would the time complexity change?"

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