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?"