Word Break - Practice Coding Problems

Word Break - Problem

Array Hash Table String Dynamic Programming Trie Memoization Medium

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

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

Input & Output

Example 1 — Basic Segmentation

$ Input: s = "leetcode", wordDict = ["leet","code"]

› Output: true

💡 Note: The string "leetcode" can be segmented as "leet code", where both "leet" and "code" are in the dictionary.

Example 2 — No Valid Segmentation

$ Input: s = "applepenapple", wordDict = ["apple","pen"]

› Output: false

💡 Note: The string cannot be segmented because "penapple" is not in the dictionary and cannot be further broken down using available words.

Example 3 — Multiple Valid Paths

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

› Output: false

💡 Note: Even though "cats", "and", "dog" are all in dictionary, we cannot form "catsandog" because "sandog" cannot be segmented.

Constraints

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
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 'leetcode' and dictionary ['leet', 'code']

Process

Find valid segmentations using dictionary words

Output

Return true if valid segmentation exists

Key Takeaway

🎯 Key Insight: Use dynamic programming to build valid segmentations incrementally by checking if each position can be reached from previous valid positions using dictionary words.

Asked in

f Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is that this is a dynamic programming problem where we build the solution incrementally. For each position, we check if we can extend any previous valid segmentation with a dictionary word. The optimal approach uses 1D Dynamic Programming with Time: O(n³), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming (Bottom-Up)	O(n³)	O(n)	Build solution iteratively from smaller subproblems
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible ways to split the string recursively
Memoization (Top-Down DP)	O(n³)	O(n)	Cache results to avoid recalculating same subproblems

Dynamic Programming (Bottom-Up) — Algorithm Steps

Create dp array where dp[i] = true if s[0:i] can be segmented
Initialize dp[0] = true (empty string)
For each position i, check all previous positions j
If dp[j] is true and s[j:i] is in dictionary, set dp[i] = true

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0] = true (empty string can always be segmented)

Fill Array

For each position, check if it can be reached from any previous valid position

Result

dp[n] contains the answer for the entire string

Code -

solution.c — C

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

bool solution(const char* s, char wordDict[][20], int dictSize) {
    int n = strlen(s);
    bool* dp = (bool*)calloc(n + 1, sizeof(bool));
    dp[0] = true;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                char word[21];
                strncpy(word, s + j, i - j);
                word[i - j] = '\0';
                
                for (int k = 0; k < dictSize; k++) {
                    if (strcmp(word, wordDict[k]) == 0) {
                        dp[i] = true;
                        goto next_i;
                    }
                }
            }
        }
        next_i:;
    }
    
    bool result = dp[n];
    free(dp);
    return result;
}

int main() {
    char s[301];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char dictLine[1000];
    fgets(dictLine, sizeof(dictLine), stdin);
    dictLine[strcspn(dictLine, "\n")] = 0;
    
    char wordDict[100][20];
    int dictSize = 0;
    
    char* token = strtok(dictLine + 1, ",");
    while (token != NULL && dictSize < 100) {
        while (*token == ' ' || *token == '"') token++;
        int len = strlen(token);
        while (len > 0 && (token[len-1] == ' ' || token[len-1] == '"' || token[len-1] == ']')) {
            token[--len] = '\0';
        }
        if (len > 0) {
            strcpy(wordDict[dictSize++], token);
        }
        token = strtok(NULL, ",");
    }
    
    bool result = solution(s, wordDict, dictSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

n positions × n previous positions to check × n substring creation time

⚠ Quadratic Growth

Space Complexity

O(n)

DP array stores boolean result for each of n positions

⚡ Linearithmic Space

89.2K Views

High Frequency

~25 min Avg. Time

2.8K 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

Dynamic Programming (Bottom-Up) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler