Word Break II - Practice Coding Problems

Word Break II - Problem

Array Hash Table String Dynamic Programming Backtracking Trie Memoization Hard

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Input & Output

Example 1 — Basic Segmentation

$ Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]

› Output: ["cats and dog","cat sand dog"]

💡 Note: Two valid ways: 'cats' + 'and' + 'dog' = 'cats and dog', and 'cat' + 'sand' + 'dog' = 'cat sand dog'

Example 2 — No Valid Segmentation

$ Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]

› Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]

💡 Note: Multiple valid combinations using different word splits

Example 3 — Single Word

$ Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

› Output: []

💡 Note: No valid segmentation possible - 'andog' cannot be formed from dictionary words

Constraints

1 ≤ s.length ≤ 20
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 10
s and wordDict[i] consist of only lowercase English letters
All strings in wordDict are unique

Visualization

Tap to expand

Understanding the Visualization

Input

String 'catsanddog' and dictionary ['cat','cats','and','sand','dog']

Process

Find all ways to split string using dictionary words

Output

All valid sentences: ['cats and dog', 'cat sand dog']

Key Takeaway

🎯 Key Insight: Use backtracking with memoization to efficiently generate all valid sentence combinations while avoiding redundant calculations

Asked in

F Facebook 85 G Google 72 a Amazon 65 M Microsoft 48

The key insight is to use backtracking/recursion to build all possible sentence combinations, with memoization to avoid recalculating the same subproblems. The memoization approach provides the best balance of correctness and efficiency. Time: O(2^n), Space: O(n × 2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(n × 2^n)	Try all possible ways to split string into dictionary words
Memoization (Top-Down DP)	O(n² × 2^n)	O(n × 2^n)	Cache results of subproblems to avoid redundant calculations
Backtracking with Early Pruning	O(2^n)	O(n)	Build solutions incrementally, backtrack when no valid continuation exists

Brute Force Recursion — Algorithm Steps

Start from beginning of string
Try each possible first word from dictionary
Recursively solve remaining substring
Combine results from all valid splits

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with full string, try each dictionary word as first word

Recurse

For each valid first word, recursively solve remaining substring

Combine

Combine first word with all solutions from remaining part

Code -

solution.c — C

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

#define MAX_WORDS 1000
#define MAX_LEN 1000
#define MAX_RESULTS 10000

char words[MAX_WORDS][MAX_LEN];
int wordCount = 0;
char results[MAX_RESULTS][MAX_LEN];
int resultCount = 0;

int isInDict(char* word) {
    for (int i = 0; i < wordCount; i++) {
        if (strcmp(words[i], word) == 0) return 1;
    }
    return 0;
}

void backtrack(char* s, int start, char* current, int len) {
    if (start == strlen(s)) {
        if (len > 0) current[len - 1] = '\0';
        strcpy(results[resultCount++], current);
        return;
    }
    
    char temp[MAX_LEN];
    for (int end = start + 1; end <= strlen(s); end++) {
        strncpy(temp, s + start, end - start);
        temp[end - start] = '\0';
        
        if (isInDict(temp)) {
            char newCurrent[MAX_LEN];
            strcpy(newCurrent, current);
            strcat(newCurrent, temp);
            strcat(newCurrent, " ");
            backtrack(s, end, newCurrent, len + strlen(temp) + 1);
        }
    }
}

int main() {
    char s[MAX_LEN];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char line[MAX_LEN];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    char* token = strtok(line + 1, ",");
    while (token != NULL) {
        while (*token == ' ' || *token == '"') token++;
        char* end = token + strlen(token) - 1;
        while (*end == ' ' || *end == '"' || *end == ']') end--;
        *(end + 1) = '\0';
        strcpy(words[wordCount++], token);
        token = strtok(NULL, ",");
    }
    
    backtrack(s, 0, "", 0);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("\"%s\"", results[i]);
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, we try every possible way to split string, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n × 2^n)

Recursion depth O(n) and potentially 2^n solutions, each taking O(n) space

⚠ Quadratic Space

125.0K Views

High Frequency

~25 min Avg. Time

5.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler