Word Break Problem in DSA Javascript - Time & Space Complexity

Time Complexity: Word Break Problem

O(n^3)

Understanding Time Complexity

We want to know 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 longer strings and bigger dictionaries?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code checks if the string s can be split into words from wordDict by building up a boolean array dp.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops checking all substrings of s.
• How many times: Outer loop runs n times, inner loop runs up to i times, totaling roughly n² substring checks.
• Each substring check uses substring and wordDict.has(), which is O(k) for substring extraction and O(1) average for dictionary lookup.

How Execution Grows With Input

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

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

Pattern observation: Doubling the input length roughly quadruples the number of operations.

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 inside nested loops.

Common Mistake

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

[OK] Correct: There are nested loops checking all possible substrings, so the work grows much faster than just one pass.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we used a Trie data structure for the dictionary instead of a hash set? 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 contains any substring from wordDict

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

C. If s is exactly equal to any word in wordDict

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

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Compare options with the problem definition

   If s can be segmented into a space-separated sequence of one or more dictionary words correctly states the problem as checking if s can be segmented into dictionary words. Other options describe partial or different checks.

3. Final Answer:

   If s can be segmented into a space-separated sequence of one or more dictionary words -> Option B

4. Quick Check:

   Word Break Problem = segmentation check [OK]

Hint: Remember: Word Break means full segmentation check [OK]

Common Mistakes:

• Thinking it checks for substring presence only
• Confusing exact match with segmentation
• Assuming reversal or partial matches

2. Which of the following is the correct way to declare a function named wordBreak in JavaScript that takes two parameters: s (string) and wordDict (array)?

easy

A. function wordBreak[s, wordDict] {}

B. def wordBreak(s, wordDict): {}

C. func wordBreak(s, wordDict) {}

D. function wordBreak(s, wordDict) {}

Solution

1. Step 1: Recall JavaScript function syntax

   In JavaScript, functions are declared using the function keyword followed by the name and parentheses enclosing parameters.

2. Step 2: Check each option's syntax

   function wordBreak(s, wordDict) {} uses correct JavaScript syntax. def wordBreak(s, wordDict): {} is Python syntax. func wordBreak(s, wordDict) {} resembles Go syntax. function wordBreak[s, wordDict] {} uses incorrect brackets.

3. Final Answer:

   function wordBreak(s, wordDict) {} -> Option D

4. Quick Check:

   JS function syntax = function name(params) {} [OK]

Hint: JS functions use parentheses for parameters, not brackets [OK]

Common Mistakes:

• Using Python or other language syntax
• Using square brackets instead of parentheses
• Missing function keyword

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

const s = "leetcode";
const wordDict = ["leet", "code"];

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

console.log(wordBreak(s, wordDict));

medium

A. undefined

B. false

C. true

D. TypeError

Solution

1. Step 1: Understand the dynamic programming array dp

   dp[i] means if substring s[0..i-1] can be segmented. dp[0] = true means empty string is segmentable.

2. Step 2: Trace the loops and substring checks

   For s = "leetcode", wordDict = ["leet", "code"], dp updates to true at dp[4] ("leet") and dp[8] ("leetcode") because both substrings are in wordDict.

3. Final Answer:

   true -> Option C

4. Quick Check:

   "leetcode" split as "leet" + "code" = true [OK]

Hint: Check dp array updates for substring matches [OK]

Common Mistakes:

• Confusing substring indices
• Not initializing dp[0] to true
• Assuming partial matches are enough

4. The following code attempts to solve the Word Break Problem but has a bug. What is the bug?

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

medium

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

B. dp[0] should be false, not true

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

D. wordDict.includes should be replaced with wordDict.indexOf

Solution

1. Step 1: Check dp array initialization

   dp array length should be s.length + 1 to include dp[s.length] index. Current length s.length causes out-of-bound errors.

2. Step 2: Verify dp usage and return statement

   dp[s.length] is accessed at return, but dp array does not have that index, causing undefined or error.

3. Final Answer:

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

4. Quick Check:

   dp length = s.length + 1 for full coverage [OK]

Hint: dp array must cover from 0 to s.length inclusive [OK]

Common Mistakes:

• Using dp length equal to s.length only
• Misunderstanding dp index meaning
• Ignoring off-by-one errors

5. Given the string s = "applepenapple" and dictionary wordDict = ["apple", "pen"], which of the following modifications to the Word Break algorithm will allow it to return true only if all possible segmentations of s are valid dictionary words (not just one)?

hard

A. Change dp to store counts of valid segmentations and check if count equals total segmentations

B. Return true as soon as one valid segmentation is found (current approach)

C. Use a stack to store all substrings and check each against wordDict once

D. Sort wordDict and use binary search for substring checks

Solution

1. Step 1: Understand current algorithm behavior

   The current algorithm returns true if at least one segmentation exists. It does not check all segmentations.

2. Step 2: Modify dp to count all valid segmentations

   By storing counts of valid segmentations at each dp index, we can compare total segmentations to valid ones. Returning true only if all segmentations are valid requires counting and comparing.

3. Final Answer:

   Change dp to store counts of valid segmentations and check if count equals total segmentations -> Option A

4. Quick Check:

   Counting all segmentations ensures all are valid [OK]

Hint: Count all segmentations, not just existence, for full validation [OK]

Common Mistakes:

• Assuming one valid segmentation means all are valid
• Ignoring need to track all segmentation paths
• Confusing substring search optimization with segmentation count