Word Break

Problem Statement

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

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

What to notice first

• You need to segment the entire string into words from the dictionary.
• Words can be reused multiple times.
• The order of words in the dictionary doesn’t matter, but coverage of the string does.
• This is a string matching problem suitable for DP or Trie-based solutions.

Examples

s	wordDict	Output	Explanation
"leetcode"	["leet","code"]	true	Can be segmented as “leet code”
"applepenapple"	["apple","pen"]	true	Can be segmented as “apple pen apple”
"catsandog"	["cat","cats","and","sand","dog"]	false	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

Real-World Applications

Where this pattern appears

• Text processing — checking if input matches valid word sequences (spell checkers, tokenizers).
• URL routing — matching URL paths against valid route patterns.
• Code parsing — verifying if a code sequence uses only valid tokens.
• Language models — determining if text can be decomposed into known vocabulary.

Complexity Comparison

Approach	Time	Space	Description
DP with Set	O(n²)	O(n + m)	Simple hash set lookup, checks all substrings
DP with Trie	O(n*k)	O(n + T)	Trie-based prefix matching, faster for overlapping words

where n = len(s), m = len(wordDict), k = max word length, T = total chars in dict

Which approach should you learn first?

• Pick DP with Set if you want the simplest implementation.
• Pick DP with Trie if you want to optimize for large dictionaries.

Simpler Logic

DP with Set

O(n²) time · O(n + m) space

Optimized for Dicts

DP with Trie

O(n*k) time · O(n + T) space

Approach 1: DP with Hash Set

★ Recommended

Use dynamic programming with a hash set for word lookup. dp[i] represents whether s[0:i] can be segmented.

For each position i, check all previous positions j where dp[j] is True, and if s[j:i] is in the dictionary, mark dp[i] as True.

⏱ Time O(n²) All substrings checked 💾 Space O(n + m) DP array + set

Step-by-step Example

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

i	s[0:i]	dp[i]	Explanation
0	""	True	Empty string is segmentable
5	”apple”	True	Found in dictionary, dp[0] = True
8	”applepen”	True	”pen” found, dp[5] = True
13	”applepenapple”	True	”apple” found, dp[8] = True

Pseudocode

function wordBreakDP(s, wordDict):
    wordSet = convert wordDict to set
    dp = array of size len(s) + 1, initialized to False
    dp[0] = True

    for i from 1 to len(s):
        for j from 0 to i:
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break

    return dp[len(s)]

Solution Code

Python

word_break_dp_set.py

from typing import List


def word_break_dp_set(s: str, word_dict: List[str]) -> bool:
    """
    Determine if string can be segmented using words from dictionary.

    Time Complexity: O(n²) where n = len(s)
    Space Complexity: O(n) for DP array + O(m) for set where m = len(word_dict)

    dp[i] = True if s[0:i] can be segmented
    For each position i, check all previous positions j where dp[j] = True
    and s[j:i] is in the word dictionary.
    """
    word_set = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True  # Empty string can be segmented

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break

    return dp[len(s)]


if __name__ == "__main__":
    print(word_break_dp_set("leetcode", ["leet", "code"]))           # True
    print(word_break_dp_set("applepenapple", ["apple", "pen"]))      # True
    print(word_break_dp_set("catsandog", ["cat", "cats", "and", "sand", "dog"]))  # False

C++

word_break_dp_set.cpp

#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

/**
 * Determine if string can be segmented using words from dictionary.
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n + m)
 */
bool wordBreakDpSet(const string& s, const vector<string>& word_dict) {
    unordered_set<string> word_set(word_dict.begin(), word_dict.end());
    vector<bool> dp(s.length() + 1, false);
    dp[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && word_set.count(s.substr(j, i - j))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length()];
}

int main() {
    cout << wordBreakDpSet("leetcode", {"leet", "code"}) << endl;  // 1
    cout << wordBreakDpSet("applepenapple", {"apple", "pen"}) << endl;  // 1
    cout << wordBreakDpSet("catsandog", {"cat", "cats", "and", "sand", "dog"}) << endl;  // 0
    return 0;
}

Java

WordBreakDpSet.java

import java.util.*;

/**
 * Determine if string can be segmented using words from dictionary.
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n + m)
 */
public class WordBreakDpSet {
    public static boolean wordBreakDpSet(String s, List<String> wordDict) {
        Set<String> wordSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(wordBreakDpSet("leetcode", Arrays.asList("leet", "code")));  // true
        System.out.println(wordBreakDpSet("applepenapple", Arrays.asList("apple", "pen")));  // true
        System.out.println(wordBreakDpSet("catsandog", Arrays.asList("cat", "cats", "and", "sand", "dog")));  // false
    }
}

JavaScript

word_break_dp_set.js

/**
 * Determine if string can be segmented using words from dictionary.
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n + m)
 */
function wordBreakDpSet(s, wordDict) {
    const wordSet = new Set(wordDict);
    const dp = new Array(s.length + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= s.length; i++) {
        for (let j = 0; j < i; j++) {
            if (dp[j] && wordSet.has(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.length];
}

console.log(wordBreakDpSet("leetcode", ["leet", "code"]));  // true
console.log(wordBreakDpSet("applepenapple", ["apple", "pen"]));  // true
console.log(wordBreakDpSet("catsandog", ["cat", "cats", "and", "sand", "dog"]));  // false

Rust

word_break_dp_set.rs

use std::collections::HashSet;

/**
 * Determine if string can be segmented using words from dictionary.
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n + m)
 */
pub fn word_break_dp_set(s: String, word_dict: Vec<String>) -> bool {
    let word_set: HashSet<&str> = word_dict.iter().map(|w| w.as_str()).collect();
    let mut dp = vec![false; s.len() + 1];
    dp[0] = true;

    for i in 1..=s.len() {
        for j in 0..i {
            if dp[j] && word_set.contains(&s[j..i]) {
                dp[i] = true;
                break;
            }
        }
    }

    dp[s.len()]
}

fn main() {
    println!("{}", word_break_dp_set("leetcode".to_string(), vec!["leet".to_string(), "code".to_string()]));  // true
    println!("{}", word_break_dp_set("applepenapple".to_string(), vec!["apple".to_string(), "pen".to_string()]));  // true
}

Go

word_break_dp_set.go

package main

import "fmt"

/*
 * Determine if string can be segmented using words from dictionary.
 *
 * Time Complexity: O(n²)
 * Space Complexity: O(n + m)
 */
func wordBreakDpSet(s string, wordDict []string) bool {
  wordSet := make(map[string]bool)
  for _, word := range wordDict {
    wordSet[word] = true
  }

  dp := make([]bool, len(s)+1)
  dp[0] = true

  for i := 1; i <= len(s); i++ {
    for j := 0; j < i; j++ {
      if dp[j] && wordSet[s[j:i]] {
        dp[i] = true
        break
      }
    }
  }

  return dp[len(s)]
}

func main() {
  fmt.Println(wordBreakDpSet("leetcode", []string{"leet", "code"}))  // true
  fmt.Println(wordBreakDpSet("applepenapple", []string{"apple", "pen"}))  // true
}

Approach 2: DP with Trie

🎯 Interview Favourite

Build a Trie from the dictionary and use it for prefix-based word matching. For each position i, traverse the Trie backward from i to find all words ending at i.

This avoids checking all substrings; instead, we only traverse valid prefixes.

⏱ Time O(n*k) Trie traversal max k chars 💾 Space O(n + T) DP array + Trie

Step-by-step Example

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

The Trie structure:

    a
    p
    p
    l
    e  (end)
    n
    ...

For position 5 (s[0:5] = “apple”):

• Traverse Trie with “apple”, find it marked as end → dp[5] = True

For position 8 (s[5:8] = “pen”):

• Traverse Trie with “pen”, find it marked as end, and dp[5] = True → dp[8] = True

Pseudocode

function wordBreakTrie(s, wordDict):
    root = build Trie from wordDict
    dp = array of size len(s) + 1, initialized to False
    dp[0] = True

    for i from 1 to len(s):
        if not dp[i]:
            node = root
            for j from i-1 down to 0:
                char = s[j]
                if char not in node.children:
                    break
                node = node.children[char]
                if dp[j] and node.is_end:
                    dp[i] = True
                    break

    return dp[len(s)]

Solution Code

Python

word_break_dp_trie.py

from typing import List


class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False


def word_break_dp_trie(s: str, word_dict: List[str]) -> bool:
    """
    Determine if string can be segmented using words from dictionary (Trie approach).

    Time Complexity: O(n*m) where n = len(s), m = max word length
    Space Complexity: O(n) for DP array + O(T) for Trie where T = total characters in dictionary

    Build a Trie from the dictionary, then use DP with Trie for faster lookups.
    dp[i] = True if s[0:i] can be segmented.
    Instead of checking all substrings (O(n²)), we traverse the Trie (O(m)).
    """
    # Build Trie
    root = TrieNode()
    for word in word_dict:
        node = root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        if not dp[i]:
            # Try to find a word ending at position i
            node = root
            for j in range(i - 1, -1, -1):
                char = s[j]
                if char not in node.children:
                    break
                node = node.children[char]
                if dp[j] and node.is_end:
                    dp[i] = True
                    break

    return dp[len(s)]


if __name__ == "__main__":
    print(word_break_dp_trie("leetcode", ["leet", "code"]))           # True
    print(word_break_dp_trie("applepenapple", ["apple", "pen"]))      # True
    print(word_break_dp_trie("catsandog", ["cat", "cats", "and", "sand", "dog"]))  # False

C++

word_break_dp_trie.cpp

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool is_end = false;
};

/**
 * Determine if string can be segmented using words from dictionary (Trie approach).
 *
 * Time Complexity: O(n*m)
 * Space Complexity: O(n + T)
 */
bool wordBreakDpTrie(const string& s, const vector<string>& word_dict) {
    TrieNode* root = new TrieNode();
    for (const string& word : word_dict) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->is_end = true;
    }

    vector<bool> dp(s.length() + 1, false);
    dp[0] = true;

    for (int i = 1; i <= s.length(); i++) {
        if (!dp[i]) {
            TrieNode* node = root;
            for (int j = i - 1; j >= 0; j--) {
                if (!node->children.count(s[j])) {
                    break;
                }
                node = node->children[s[j]];
                if (dp[j] && node->is_end) {
                    dp[i] = true;
                    break;
                }
            }
        }
    }

    return dp[s.length()];
}

int main() {
    cout << wordBreakDpTrie("leetcode", {"leet", "code"}) << endl;  // 1
    cout << wordBreakDpTrie("applepenapple", {"apple", "pen"}) << endl;  // 1
    cout << wordBreakDpTrie("catsandog", {"cat", "cats", "and", "sand", "dog"}) << endl;  // 0
    return 0;
}

Java

WordBreakDpTrie.java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean is_end = false;
}

/**
 * Determine if string can be segmented using words from dictionary (Trie approach).
 *
 * Time Complexity: O(n*m)
 * Space Complexity: O(n + T)
 */
public class WordBreakDpTrie {
    public static boolean wordBreakDpTrie(String s, List<String> wordDict) {
        TrieNode root = new TrieNode();
        for (String word : wordDict) {
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
                node.children.putIfAbsent(ch, new TrieNode());
                node = node.children.get(ch);
            }
            node.is_end = true;
        }

        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for (int i = 1; i <= s.length(); i++) {
            if (!dp[i]) {
                TrieNode node = root;
                for (int j = i - 1; j >= 0; j--) {
                    char ch = s.charAt(j);
                    if (!node.children.containsKey(ch)) {
                        break;
                    }
                    node = node.children.get(ch);
                    if (dp[j] && node.is_end) {
                        dp[i] = true;
                        break;
                    }
                }
            }
        }

        return dp[s.length()];
    }

    public static void main(String[] args) {
        System.out.println(wordBreakDpTrie("leetcode", Arrays.asList("leet", "code")));  // true
        System.out.println(wordBreakDpTrie("applepenapple", Arrays.asList("apple", "pen")));  // true
        System.out.println(wordBreakDpTrie("catsandog", Arrays.asList("cat", "cats", "and", "sand", "dog")));  // false
    }
}

JavaScript

word_break_dp_trie.js

class TrieNode {
    constructor() {
        this.children = new Map();
        this.is_end = false;
    }
}

/**
 * Determine if string can be segmented using words from dictionary (Trie approach).
 *
 * Time Complexity: O(n*m)
 * Space Complexity: O(n + T)
 */
function wordBreakDpTrie(s, wordDict) {
    const root = new TrieNode();

    for (const word of wordDict) {
        let node = root;
        for (const ch of word) {
            if (!node.children.has(ch)) {
                node.children.set(ch, new TrieNode());
            }
            node = node.children.get(ch);
        }
        node.is_end = true;
    }

    const dp = new Array(s.length + 1).fill(false);
    dp[0] = true;

    for (let i = 1; i <= s.length; i++) {
        if (!dp[i]) {
            let node = root;
            for (let j = i - 1; j >= 0; j--) {
                const ch = s[j];
                if (!node.children.has(ch)) {
                    break;
                }
                node = node.children.get(ch);
                if (dp[j] && node.is_end) {
                    dp[i] = true;
                    break;
                }
            }
        }
    }

    return dp[s.length];
}

console.log(wordBreakDpTrie("leetcode", ["leet", "code"]));  // true
console.log(wordBreakDpTrie("applepenapple", ["apple", "pen"]));  // true
console.log(wordBreakDpTrie("catsandog", ["cat", "cats", "and", "sand", "dog"]));  // false

Rust

word_break_dp_trie.rs

use std::collections::HashMap;

#[derive(Clone)]
struct TrieNode {
    children: HashMap<char, Box<TrieNode>>,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_end: false,
        }
    }
}

/**
 * Determine if string can be segmented using words from dictionary (Trie approach).
 *
 * Time Complexity: O(n*m)
 * Space Complexity: O(n + T)
 */
pub fn word_break_dp_trie(s: String, word_dict: Vec<String>) -> bool {
    let mut root = TrieNode::new();

    for word in word_dict {
        let mut node = &mut root;
        for ch in word.chars() {
            node = &mut node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new()));
        }
        node.is_end = true;
    }

    let mut dp = vec![false; s.len() + 1];
    dp[0] = true;

    for i in 1..=s.len() {
        if !dp[i] {
            let mut node = &root;
            for j in (0..i).rev() {
                if let Some(next) = node.children.get(&s.chars().nth(j).unwrap()) {
                    node = next;
                    if dp[j] && node.is_end {
                        dp[i] = true;
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }

    dp[s.len()]
}

fn main() {
    println!("{}", word_break_dp_trie("leetcode".to_string(), vec!["leet".to_string(), "code".to_string()]));  // true
}

Go

word_break_dp_trie.go

package main

import "fmt"

type TrieNode struct {
  children map[rune]*TrieNode
  is_end   bool
}

func NewTrieNode() *TrieNode {
  return &TrieNode{
    children: make(map[rune]*TrieNode),
    is_end:   false,
  }
}

/*
 * Determine if string can be segmented using words from dictionary (Trie approach).
 *
 * Time Complexity: O(n*m)
 * Space Complexity: O(n + T)
 */
func wordBreakDpTrie(s string, wordDict []string) bool {
  root := NewTrieNode()

  for _, word := range wordDict {
    node := root
    for _, ch := range word {
      if _, exists := node.children[ch]; !exists {
        node.children[ch] = NewTrieNode()
      }
      node = node.children[ch]
    }
    node.is_end = true
  }

  chars := []rune(s)
  dp := make([]bool, len(chars)+1)
  dp[0] = true

  for i := 1; i <= len(chars); i++ {
    if !dp[i] {
      node := root
      for j := i - 1; j >= 0; j-- {
        ch := chars[j]
        if next, exists := node.children[ch]; exists {
          node = next
          if dp[j] && node.is_end {
            dp[i] = true
            break
          }
        } else {
          break
        }
      }
    }
  }

  return dp[len(chars)]
}

func main() {
  fmt.Println(wordBreakDpTrie("leetcode", []string{"leet", "code"}))  // true
  fmt.Println(wordBreakDpTrie("applepenapple", []string{"apple", "pen"}))  // true
}

Common mistakes

Watch for these pitfalls

• Forgetting to initialize dp[0] = True (empty string is always segmentable).
• Not converting wordDict to a set, leading to O(m) lookup instead of O(1).
• Breaking the inner loop prematurely without ensuring all valid splits are checked.
• In the Trie approach, traversing forward instead of backward (use reverse order to build correctly).

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

word_break_space_optimized.py

"""
Solution for Word Break
"""

def solve():
    """Implementation for approach 3 of Word Break"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

word_break_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Word Break
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

WordBreakSpaceOptimized.java

/**
 * Solution for Word Break
 * Approach 3
 */
public class WordBreakSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

word_break_space_optimized.js

/**
 * Solution for Word Break
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

word_break_space_optimized.rs

/// Solution for Word Break
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

word_break_space_optimized.go

package main

import "fmt"

// Solution for Word Break
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Word Break II ↗ Hard #140
• Implement Trie (Prefix Tree) ↗ Medium #208
• Word Search II ↗ Hard #212
• Climbing Stairs ↗ Easy #70

Interview Tips

Key trade-offs to discuss

• Why DP over backtracking? DP avoids redundant recomputation of subproblems, reducing exponential time.
• Set vs Trie: Set is simpler but checks all O(n²) substrings. Trie is faster for many short words.
• Space-time tradeoff: Trie uses more memory (building the tree) but saves time on lookups.
• Edge cases: empty string (True), single word matching entire string, word reuse, etc.

← Previous
#138 Copy List with Random Pointer Next
#140 Word Break II →