Word Break Problem in DSA C

Mental Model

We want to check if a string can be split into valid words from a dictionary. We try breaking the string at every position and see if the left part is a word and the right part can also be split.

Analogy: Imagine you have a long sentence without spaces and a list of known words. You try to put spaces in different places to see if the sentence can be made up of those known words.

string: w o r d b r e a k
dictionary: [word, break, problem]

Initial:
"wordbreak"

Try splits:
[word] + [break]
[wordb] + [reak]
[wordbr] + [eak]
...

Dry Run Walkthrough

Input: string: "wordbreak", dictionary: ["word", "break", "problem"]

Goal: Determine if "wordbreak" can be segmented into dictionary words

Step 1: Check prefix "w" - not in dictionary, move to next prefix

"w" (not word), continue checking prefixes

Step 2: Check prefix "wo" - not in dictionary, move to next prefix

"wo" (not word), continue checking prefixes

Step 3: Check prefix "wor" - not in dictionary, move to next prefix

"wor" (not word), continue checking prefixes

Step 4: Check prefix "word" - found in dictionary, now check suffix "break"

"word" (word), suffix "break" to check

Step 5: Check suffix "break" - found in dictionary, so "wordbreak" can be segmented

"word" + "break" both words, success

Result:

"word" -> "break" -> null (string can be segmented)

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// Check if word is in dictionary
bool isInDict(const char* word, const char* dict[], int dictSize) {
    for (int i = 0; i < dictSize; i++) {
        if (strcmp(word, dict[i]) == 0) {
            return true;
        }
    }
    return false;
}

// Word Break function using recursion and memoization
bool wordBreakHelper(const char* s, const char* dict[], int dictSize, int start, int memo[]) {
    int len = strlen(s);
    if (start == len) {
        return true; // reached end successfully
    }
    if (memo[start] != -1) {
        return memo[start]; // return cached result
    }
    for (int end = start + 1; end <= len; end++) {
        int subLen = end - start;
        char sub[subLen + 1];
        strncpy(sub, s + start, subLen);
        sub[subLen] = '\0';
        if (isInDict(sub, dict, dictSize)) {
            if (wordBreakHelper(s, dict, dictSize, end, memo)) {
                memo[start] = 1;
                return true;
            }
        }
    }
    memo[start] = 0;
    return false;
}

bool wordBreak(const char* s, const char* dict[], int dictSize) {
    int len = strlen(s);
    int memo[len];
    for (int i = 0; i < len; i++) {
        memo[i] = -1; // -1 means not computed
    }
    return wordBreakHelper(s, dict, dictSize, 0, memo);
}

int main() {
    const char* dict[] = {"word", "break", "problem"};
    const char* s = "wordbreak";
    if (wordBreak(s, dict, 3)) {
        printf("word break possible\n");
    } else {
        printf("word break not possible\n");
    }
    return 0;
}

if (start == len) { return true; }

base case: reached end means successful segmentation

if (memo[start] != -1) { return memo[start]; }

use memo to avoid repeated work

for (int end = start + 1; end <= len; end++) { ... }

try all prefixes from current start

if (isInDict(sub, dict, dictSize)) { if (wordBreakHelper(...)) { memo[start] = true; return true; } }

if prefix is word and suffix can be segmented, mark true and return

memo[start] = false; return false;

no valid segmentation found from this start

Output

word break possible

Complexity Analysis

Time: O(n^3) because for each start index we try all end indices and substring copying takes O(n)

Space: O(n) for memoization array to store results for each start index

vs Alternative: Naive recursion without memoization is exponential because it recomputes subproblems many times

Edge Cases

empty string

returns true because empty string can be segmented trivially

DSA C

if (start == len) { return true; }

string with no matching dictionary words

returns false as no segmentation possible

DSA C

memo[start] = false; return false;

string equals a dictionary word

returns true immediately

DSA C

if (start == len) { return true; }

When to Use This Pattern

When you need to check if a string can be split into valid dictionary words, use the Word Break pattern with recursion and memoization to efficiently explore all splits.

Common Mistakes

Mistake: Not using memoization causing exponential time and timeout
Fix: Add a memo array to store results for each start index and reuse them

Mistake: Not checking the base case when start reaches string length
Fix: Add base case: if start == length, return true

Mistake: Incorrect substring extraction causing wrong comparisons
Fix: Use strncpy carefully and null-terminate substring before dictionary check

Summary

Checks if a string can be split into dictionary words by trying all prefixes and recursively checking suffixes.

Use when you want to validate if a string can be segmented into known words.

The key insight is to try every prefix and remember results to avoid repeated work.