⭐️ (Medium) 139. Word Break, NeetCode 75

https://leetcode.com/problems/word-break/

Last review: Aug 20, 2025 Next review: Decent, but it wasn’t smooth enough. Remember to explain the time complexity when you practice.

Check whether the string s can be fully constructed using words from wordDict, where each word in wordDict can be used multiple times.

(The problem is not asking: whether every word in wordDict appears in s.)

Similar Description Problem

• ⭐️ (Hard) 212. Word Search II, NeetCode 75

Examples

s = "leetcode", wordDict = ["leet","code"]
Segment: "leet code", Result: true

s = "leetcode", wordDict = ["code","leet"]
Segment: "leet code", Result: true
WHY: Order is not the point

s = "codeleet", wordDict = ["leet","code"]
Segment: "code leet", Result: true
WHY: Order is not the point

s = "leetcodeleet", wordDict = ["leet","code"]
Segment: "leet code leet", Result: true
WHY: We can reuse words in `wordDict` to match segment

s = "leet", wordDict = ["leet","code"]
Segment: "leet", Result: true
WHY: The segment can be matched

s = "leetcode", wordDict = ["leet"]
Segment: "leet code", Result: false
WHY: The segment can not be matched (`s` can not be segmented into less than one dictionary words)

X No Such Case:
s = "leetcode", wordDict = ["leet", "leet", "code"]
Constraint: All the strings of wordDict are unique)

DFS (Return-Value) + Hash Map

• Time Complexity O(~wordMax^n)
  • At each layer of DFS, it has up to wordMax choices
• Space Complexity O(n)

func wordBreak(s string, wordDict []string) bool {

	var wordMaxLen int
	wordMap := make(map[string]bool)
	for _, word := range wordDict {
		wordMap[word] = true
		wordMaxLen = max(wordMaxLen, len(word))
	}

	// i: next index
	var dfs func(i int) bool
	dfs = func(i int) bool {
		if i == len(s) {
			return true
		}

		for j := i; j < len(s) && len(s[i:j+1]) <= wordMaxLen; j++ {
			word := s[i : j+1]
			if wordMap[word] {
				if dfs(i + len(word)) {
					return true
				}
			}
		}
		return false
	}

	return dfs(0)
}

DFS (Return-Value) + Trie

• Time Complexity O(~wordMax^n)
  • At each layer of DFS, it has up to wordMax choices
• Space Complexity O(n)

func wordBreak(s string, wordDict []string) bool {

	trie := NewTrie()
	var wordMaxLen int
	for _, word := range wordDict {
		trie.Insert(word)
		wordMaxLen = max(wordMaxLen, len(word))
	}

	// i: next index
	var dfs func(i int) bool
	dfs = func(i int) bool {
		if i == len(s) {
			return true
		}
		for j := i; j < len(s) && len(s[i:j+1]) <= wordMaxLen; j++ {
			word := s[i : j+1]
			if trie.Search(word) && dfs(i+len(word)) {
				return true
			}
		}
		return false
	}

	return dfs(0)
}

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

type Trie struct {
	root *TrieNode
}

func NewTrie() Trie {
	return Trie{
		root: &TrieNode{children: make(map[rune]*TrieNode)},
	}
}

func (t *Trie) Search(word string) bool {
	cur := t.root
	for _, r := range word {
		if cur.children[r] == nil {
			return false
		}
		cur = cur.children[r]
	}
	return cur.isWord
}

func (t *Trie) Insert(word string) {
	cur := t.root
	for _, r := range word {
		if cur.children[r] == nil {
			cur.children[r] = &TrieNode{children: make(map[rune]*TrieNode)}
		}
		cur = cur.children[r]
	}
	cur.isWord = true
}

DFS (Return-Value) + Hash Map + DP ⭐️

• Time Complexity O(n * wordMax)
  • Each index needs have to try out up to wordMax length, but we don’t need to recalculate the visited indices again.
• Space Complexity O(n)