Word Break and Segment String
Use a 1D DP table to determine if a string can be segmented into dictionary words, analysing the O(n²) time and why a trie speeds it up.
Word Break and Segment String is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Word Break Problem
Word Break (LeetCode 139) asks: given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, with s = 'leetcode' and wordDict = ['leet', 'code'], the answer is True because 'leet' + 'code' = 'leetcode'. This is a classic 1D DP problem.
s = 'leetcode'
word_set = {'leet', 'code'}
# Can we split 'leetcode' into words from word_set?
# 'leet' in set → yes, 'code' in set → yes
# So: 'leetcode' = 'leet' + 'code' → True
s2 = 'catsandog'
word_set2 = {'cats', 'dog', 'sand', 'and', 'cat'}
# No matter how we split, last part 'og' not in dict
print('Expected: True, False')DP Formulation and State
Define dp[i] as True if the substring s[:i] can be segmented using the dictionary. The base case is dp[0] = True (the empty string is always segmentable). For each position i, check all positions j < i: if dp[j] is True and s[j:i] is in the dictionary, then dp[i] = True. The final answer is dp[len(s)].
def word_break(s, word_dict):
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True # empty string
for i in range(1, n + 1):
for j in range(i):
# If s[:j] is segmentable AND s[j:i] is a word
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # no need to check other j values
return dp[n]
print(word_break('leetcode', ['leet', 'code'])) # True
print(word_break('catsandog', ['cats','dog','sand','and','cat'])) # FalseTracing the DP Table
For s = 'leetcode' and dict {'leet', 'code'}: dp[0]=T. At i=4: j=0, dp[0]=T and s[0:4]='leet' in dict → dp[4]=T. At i=8: j=4, dp[4]=T and s[4:8]='code' in dict → dp[8]=T. All other positions where no word ends remain False. The answer dp[8]=True confirms the string is segmentable.
def word_break_trace(s, word_dict):
word_set = 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 word_set:
dp[i] = True
print(f'dp[{i}]=True via s[{j}:{i}]={repr(s[j:i])}')
break
print('dp table:', dp)
return dp[n]
word_break_trace('leetcode', ['leet', 'code'])Time Complexity Analysis
The naive DP runs in O(n²) time: n outer iterations times up to n inner iterations. However, slicing s[j:i] also costs O(n), making the actual complexity O(n³) in Python. One optimisation is to iterate over words in the dictionary and check if each word ends at position i, giving O(n × W × L) where W is dictionary size and L is average word length. For most interview inputs, O(n²) or O(n³) is acceptable.
# Slightly faster: iterate over words rather than all j positions
def word_break_v2(s, word_dict):
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for word in word_set:
wl = len(word)
# Does 'word' end exactly at position i?
if i >= wl and dp[i - wl] and s[i - wl:i] == word:
dp[i] = True
break
return dp[n]
print(word_break_v2('applepenapple', ['apple', 'pen'])) # TrueMemoised Recursion Alternative
The same problem can be solved top-down with memoisation. Define a recursive function can_break(start) that returns True if s[start:] is segmentable. Try each word as a prefix of s[start:] and recurse on the remainder. Cache results to avoid re-exploring the same starting index multiple times. This is equivalent to the bottom-up DP but can be faster in practice if many positions are pruned early.
from functools import lru_cache
def word_break_memo(s, word_dict):
word_set = set(word_dict)
@lru_cache(maxsize=None)
def can_break(start):
if start == len(s): return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(word_break_memo('leetcode', ['leet', 'code'])) # True
print(word_break_memo('catsandog', ['cats','dog','sand','and','cat'])) # FalseReturning All Valid Segmentations
Word Break II (LeetCode 140) asks for all possible segmentations. The approach is backtracking with memoisation: recurse from each position and, when a word matches, recurse on the remainder. Store all partial results as lists of strings. To avoid TLE, memoize the list of sentences possible from each starting index. The number of sentences can be exponential in the worst case, but memoisation eliminates redundant computation.
from functools import lru_cache
def word_break_ii(s, word_dict):
word_set = set(word_dict)
@lru_cache(maxsize=None)
def break_from(start):
if start == len(s): return ['']
results = []
for end in range(start + 1, len(s) + 1):
word = s[start:end]
if word in word_set:
for rest in break_from(end):
results.append(word if not rest else word + ' ' + rest)
return results
return break_from(0)
print(word_break_ii('catsanddog', ['cat','cats','and','sand','dog']))
# ['cat sand dog', 'cats and dog']Trie Optimisation
When the dictionary is large or words are long, checking s[j:i] in word_set for all j is slow due to Python string hashing. A Trie allows you to walk the trie character by character, pruning impossible paths early. Instead of checking all O(n) starting positions, you only follow paths that exist in the trie. This reduces practical runtime significantly when few prefixes lead to valid words.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def build_trie(words):
root = TrieNode()
for word in words:
node = root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
node.is_end = True
return root
def word_break_trie(s, word_dict):
root = build_trie(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(n):
if not dp[i]: continue
node = root
for j in range(i, n):
ch = s[j]
if ch not in node.children: break
node = node.children[ch]
if node.is_end:
dp[j + 1] = True
return dp[n]
print(word_break_trie('leetcode', ['leet', 'code'])) # TrueEdge Cases and Constraints
Important edge cases: (1) Empty string: return True (empty string is trivially segmentable). (2) Word not in dictionary: dp never sets the corresponding position True, returns False correctly. (3) Overlapping words: e.g., 'a' and 'aa' in dict with s='aaa' — the DP handles this naturally by checking all j values. (4) Repeated characters: s='aaaaab' with dict=['a','aa','aaa'] — exponential paths but memoisation caps it at O(n²).
def word_break(s, word_dict):
word_set = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True
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)]
# Edge cases
print(word_break('', ['hello'])) # True (empty string)
print(word_break('a', ['b'])) # False
print(word_break('aaa', ['a', 'aa'])) # True (many ways)Segment String Generalisation
Word Break generalises to any string segmentation problem: can string s be partitioned according to some rule? Replace the dictionary lookup with any O(1) or O(L) check. For instance: can s be partitioned into palindromes? Use a precomputed palindrome table instead of a word set. The DP structure is identical — only the validity check changes.
def palindrome_partition_possible(s):
'''Can s be partitioned into palindromes? (Always yes — single chars are palindromes)'''
n = len(s)
# Precompute palindrome table
is_pal = [[False]*n for _ in range(n)]
for i in range(n): is_pal[i][i] = True
for i in range(n-1): is_pal[i][i+1] = (s[i]==s[i+1])
for length in range(3, n+1):
for i in range(n-length+1):
j = i + length - 1
is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1]
# DP similar to word break
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and is_pal[j][i-1]:
dp[i] = True
break
return dp[n]
print(palindrome_partition_possible('aab')) # True (a,a,b or aa,b)DP vs BFS Approach
Word Break can also be framed as a BFS shortest-path problem: each position in the string is a node, and there is an edge from j to i if s[j:i] is in the dictionary. BFS from node 0 asks whether node n is reachable. BFS gives the same O(n² × L) complexity but may be more intuitive if you model it as a graph problem during an interview.
from collections import deque
def word_break_bfs(s, word_dict):
word_set = set(word_dict)
n = len(s)
visited = set()
queue = deque([0])
while queue:
start = queue.popleft()
if start == n: return True
for end in range(start + 1, n + 1):
if end not in visited and s[start:end] in word_set:
visited.add(end)
queue.append(end)
return False
print(word_break_bfs('leetcode', ['leet', 'code'])) # True
print(word_break_bfs('catsandog', ['cats','dog','and','sand','cat'])) # FalseInterview Communication Strategy
In an interview, walk through this thought process: (1) Observe that choices at each position depend on what was reachable before — this signals DP. (2) Define the state: dp[i] = can we segment s[:i]? (3) State the recurrence and base case before coding. (4) Code the O(n²) solution first, then mention the Trie optimisation as a follow-up. (5) Discuss edge cases: empty string, single character, word not in dictionary.
# Clean final solution to present in interview
def word_break(s, word_dict):
'''O(n^2 * L) time, O(n + W) space where W = total word length in dict'''
word_set = set(word_dict) # O(W) space
n = len(s)
dp = [False] * (n + 1) # O(n) space
dp[0] = True
for i in range(1, n + 1):
for j in range(i): # try all split points
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]
# Time: O(n^2 * L) - n^2 pairs, each dict lookup is O(L)
# Space: O(n) for dp array, O(W) for word_set
print(word_break('applepenapple', ['apple', 'pen'])) # TrueQuick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: dp[i] represents whether s[:i] can be segmented into dictionary words, the O(n²) recurrence checks all split points j where dp[j]=True and s[j:i] is in the word set, and a Trie can accelerate the inner loop by pruning non-existent prefixes early. Next up we explore Decode Ways and Counting Paths, another Fibonacci-like 1D DP pattern.
Frequently asked questions
Is the “Word Break and Segment String” lesson free?
Yes — the full text of “Word Break and Segment String” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Word Break and Segment String”?
Use a 1D DP table to determine if a string can be segmented into dictionary words, analysing the O(n²) time and why a trie speeds it up. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Word Break and Segment String” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- House Robber: Take-or-Skip Recurrence
- Maximum Subarray and Maximum Product Subarray
- Word Break and Segment String
- Decode Ways and Counting Paths