Word Break Problem in DSA C - Time & Space Complexity

Time Complexity: Word Break Problem

O(n^2 * m * k)

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.

bool wordBreak(char* s, char** wordDict, int wordDictSize) {
    int n = strlen(s);
    bool dp[n+1];
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        dp[i] = false;
        for (int j = 0; j < i; j++) {
            if (dp[j] && isInDict(s + j, i - j, wordDict, wordDictSize)) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

// Helper function checks if substring s of length len is in wordDict
bool isInDict(char* s, int len, char** wordDict, int wordDictSize) {
    for (int k = 0; k < wordDictSize; k++) {
        if (strlen(wordDict[k]) == len && strncmp(s, wordDict[k], len) == 0) {
            return true;
        }
    }
    return false;
}
    

This code checks if the input 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; inner loop runs up to n times for each outer iteration.
• Additional work: For each substring checked, we scan the dictionary to find a match.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 10 * 10 * wordDictSize checks
100	About 100 * 100 * wordDictSize checks
1000	About 1000 * 1000 * wordDictSize checks

Pattern observation: Operations grow roughly with the square of the input length multiplied by dictionary size.

Final Time Complexity

Time Complexity: O(n^2 * m * k)

This means the time grows roughly with the square of the string length (n), times the number of words in the dictionary (m), times the average length of dictionary words (k).

Common Mistake

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

[OK] Correct: The code uses nested loops and checks many substrings against the dictionary, 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 and dictionary lookups clearly.

Self-Check

"What if we used a hash set for the dictionary to check words in constant time? How would the time complexity change?"