Word Break

Word Break is a popular dynamic programming question. Dynamic programming is a way to solve a big problem by breaking it into small pieces, solving each piece once, and saving the answer. This one feels like a word puzzle. But it hides the same repeated work that all dynamic programming problems have. So it tests if you can find that repeat and remove it.

🎯 The Problem

You get a string and a list of allowed words, called a dictionary. Here are the rules.

• You must cut the string into pieces.
• Every piece must be a word in the dictionary.
• You can reuse a word as many times as you like.
• You return a true or false answer. No need to show the pieces.

For the string "leetcode" and the dictionary ["leet", "code"], you can cut it as leet plus code. Both are in the dictionary. So the answer is true.

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

Explanation: "leetcode" can be split into "leet" and "code", both in the dictionary.

This diagram shows the cut. We split the string at one spot and check both pieces.

🐢 Approach 1: Plain Recursion (Brute Force)

The idea in one line: try every cut, and if any chain of cuts uses the whole string, answer true.

The idea:

• Start at the front of the string.
• Try every possible first word.
• If the front part is a dictionary word, solve the rest the same way.

How it works:

• Write a function that, from a start position, returns whether the rest can be broken.
• It tries each end point. If the piece from start to that end is a word, it recurses on the remaining part.
• If the start reaches the end of the string, the whole string is used up, so return true.

Why it is weak:

• The same start position gets checked again and again from different paths.
• These repeated checks are overlapping subproblems, the same small case appearing many times.
• The branching grows fast, so it is about O(2ⁿ). Too slow.

Here is the plain recursion code:

def word_break(s, word_dict):
    words = set(word_dict)

    def dfs(index):
        if index == len(s):
            return True
        for end in range(index + 1, len(s) + 1):
            if s[index:end] in words and dfs(end):
                return True
        return False

    return dfs(0)

⚡ Approach 2: Memoization (Better)

The idea in one line: save each position’s answer so you never solve it twice.

The idea:

• Keep an array memo where memo[i] says whether the string starting at i can be broken.

How it works:

• The first time we solve a position, we store true or false.
• The next time, we read it back instead of recomputing.
• This is memoization, remembering a function result so you never compute it twice.

Why it is faster:

• Each position is solved once.
• The time drops to about O(n²).

Here is the memoized recursion:

from functools import lru_cache


def word_break(s, word_dict):
    words = set(word_dict)

    @lru_cache(None)
    def dfs(index):
        if index == len(s):
            return True
        return any(s[index:end] in words and dfs(end) for end in range(index + 1, len(s) + 1))

    return dfs(0)

⚡ Approach 3: Bottom-Up Tabulation (Better)

The idea in one line: build the answer from the smallest prefixes up to the full string.

The idea:

• Tabulation fills a table from the smallest cases toward the answer.
• Make a boolean array dp of size n+1.
• dp[i] is true if the first i characters can be fully broken into dictionary words.

How it works:

• Set dp[0] to true. An empty string needs no words.
• For each end point i, look at every split point j before it.
• If dp[j] is true and the piece from j to i is in the dictionary, then dp[i] is true.
• The answer is dp[n].

Why it is solid:

• No recursion stack.
• Each end point is filled once.

This diagram shows the dp table filling for "leetcode". The true cells chain together to the end.

🚀 Approach 4: Tabulation With a Word Set (Best)

The idea in one line: keep the tabulation, but check membership in a set so each lookup is fast.

The idea:

• The plain dictionary is a list, and checking a list is slow.
• Put the words into a set, a structure that checks membership almost instantly.

How it works:

• Build the same dp table as before.
• Each “is this piece a word?” check hits the set, not a list scan.

Why it is best:

• The two nested position loops still make it O(n²).
• But each lookup is now quick instead of a slow scan.
• This is the version you write in the interview.

Steps to Solve

1. Put every dictionary word into a set for fast lookups.
2. Make a boolean array dp of size n+1, all false, then set dp[0] to true.
3. Walk the end point i from 1 to n.
4. For each i, walk a split point j from 0 up to i.
5. If dp[j] is true and the piece from j to i is in the set, set dp[i] true and stop the inner loop.
6. The answer is dp[n].

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

bool inDict(char *piece, char *dict[], int dictSize) {
    for (int k = 0; k < dictSize; k++) {
        if (strcmp(piece, dict[k]) == 0) {
            return true;       // piece matches a word
        }
    }
    return false;
}

bool wordBreak(char *s, char *dict[], int dictSize) {
    int n = strlen(s);
    bool dp[100];
    memset(dp, 0, sizeof(dp));
    dp[0] = true;              // empty prefix is breakable
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                char piece[100];
                strncpy(piece, s + j, i - j);   // piece from j to i
                piece[i - j] = '\0';
                if (inDict(piece, dict, dictSize)) {
                    dp[i] = true;
                    break;
                }
            }
        }
    }
    return dp[n];
}

int main(void) {
    char *dict[] = {"leet", "code"};
    char s[] = "leetcode";
    printf("%s\n", wordBreak(s, dict, 2) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> words(wordDict.begin(), wordDict.end());
    int n = s.size();
    vector<bool> dp(n + 1, false);
    dp[0] = true;              // empty prefix is breakable
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && words.count(s.substr(j, i - j))) {
                dp[i] = true;  // piece j..i is a word
                break;
            }
        }
    }
    return dp[n];
}

int main() {
    vector<string> wordDict = {"leet", "code"};
    string s = "leetcode";
    cout << (wordBreak(s, wordDict) ? "true" : "false") << endl;
    return 0;
}

true

import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class WordBreak {
    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;              // empty prefix is breakable
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && words.contains(s.substring(j, i))) {
                    dp[i] = true;  // piece j..i is a word
                    break;
                }
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        List<String> wordDict = List.of("leet", "code");
        String s = "leetcode";
        System.out.println(wordBreak(s, wordDict));
    }
}

true

def word_break(s, word_dict):
    words = set(word_dict)        # fast lookups
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True                  # empty prefix is breakable
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True      # piece j..i is a word
                break
    return dp[n]


s = "leetcode"
word_dict = ["leet", "code"]
print(word_break(s, word_dict))

True

function wordBreak(s, wordDict) {
  const words = new Set(wordDict); // fast lookups
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // empty prefix is breakable
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && words.has(s.slice(j, i))) {
        dp[i] = true; // piece j..i is a word
        break;
      }
    }
  }
  return dp[n];
}

const s = "leetcode";
const wordDict = ["leet", "code"];
console.log(wordBreak(s, wordDict));

true

Let us walk through the Python version line by line and see why each piece is there.

def word_break(s, word_dict):
    words = set(word_dict)
    n = len(s)
    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[n]

The line words = set(word_dict) turns the list into a set. A set checks if a word is inside it almost instantly. A plain list would scan every word, which is slow.

The line dp = [False] * (n + 1) makes our table. Here dp[i] is true if the first i characters can be fully broken into dictionary words. We need n + 1 slots so we have one for the empty prefix and one for each character. The line dp[0] = True sets the base. An empty string needs no words, so it is always breakable.

The outer loop for i in range(1, n + 1) picks the end of the prefix we are checking. The inner loop for j in range(i) picks a split point inside that prefix. The check if dp[j] and s[j:i] in words is the heart of it. It asks two things. Is the part before j already breakable. And is the piece from j to i a dictionary word. If both are true, then the whole prefix up to i is breakable, so we set dp[i] = True.

The break stops the inner loop early once we found one good split. We do not need more. The final dp[n] is the answer for the whole string. Trace "leetcode". We get dp[0] true. Then dp[4] true because leet is a word and dp[0] is true. Then dp[8] true because code is a word and dp[4] is true. So the answer is true.

⏱️ Time and Space Complexity

Plain recursion repeats work, so it is O(2ⁿ). Memoization and tabulation each have two nested position loops, so they are O(n²) on the positions, times the cost of slicing and checking a piece. The space is O(n) for the dp table plus the word set. So the optimized tabulation lands at O(n²) time in the usual analysis.

🧩 Key Takeaways

• ✅ The question is a yes or no. Can the string be cut into pieces that are all dictionary words.
• ✅ dp[i] is true if the first i characters can be fully broken. Start with dp[0] true for the empty string.
• ✅ For each end point, look at every split point before it. Both halves must work for the prefix to work.
• ✅ Plain recursion repeats overlapping subproblems, so it is O(2ⁿ). Saving answers brings it to O(n²).
• ✅ Put the dictionary in a set so each piece check is almost instant.

🚀 What’s Next?

• Longest Increasing Subsequence
• Min Cost Climbing Stairs