Word Break
MedPrompt
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 that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
Note that you are allowed to reuse a dictionary word.Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Constraints:
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare unique.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive function to check all possible ways of segmenting the string. For each possible prefix that is a valid word in the dictionary, it recursively checks if the remaining suffix can also be segmented.
Algorithm
- Create a
HashSetfrom thewordDictforO(1)average time lookups. - Define a recursive helper function
wb(s, wordSet). - Base Case: If
sis empty, returntrue. - Iterate with an index
ifrom 1 tos.length(). - In each iteration, get the prefix
s.substring(0, i). - Check if the
wordSetcontains this prefix. - If it does, recursively call
wbwith the suffixs.substring(i). - If the recursive call returns
true, returntruefrom the current function. - If the loop completes without returning, it means no valid segmentation was found starting with any prefix. Return
false.
Walkthrough
The core idea is to define a function, say canBreak(s), which returns true if string s can be segmented and false otherwise.
The base case for the recursion is an empty string. An empty string signifies that the original string has been successfully segmented completely. Thus, canBreak("") returns true.
For a non-empty string s, we iterate through all its prefixes. If a prefix p is found in the wordDict, we make a recursive call on the rest of the string (the suffix).
If the recursive call on the suffix returns true, it means we have found a valid segmentation for the original string, and we can immediately return true.
If we exhaust all possible prefixes and none lead to a successful segmentation, the function returns false.
To make dictionary lookups efficient, the wordDict is first converted into a HashSet.
public class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); return wb(s, wordSet); } private boolean wb(String s, Set<String> wordSet) { if (s.isEmpty()) { return true; } for (int i = 1; i <= s.length(); i++) { if (wordSet.contains(s.substring(0, i)) && wb(s.substring(i), wordSet)) { return true; } } return false; }}Complexity
Time
O(2^n)
Space
O(n)
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem's recursive definition.
Cons
Extremely inefficient due to a large number of redundant computations for the same substrings.
Leads to a "Time Limit Exceeded" (TLE) error on most platforms for non-trivial inputs.
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. This avoids re-computing the answer for the same substring multiple times, which is the major drawback of the brute-force method.
Algorithm
- Create a memoization array,
memo, of sizes.length(). We can use aBooleanarray initialized tonulls to represent three states: not computed (null), can be segmented (true), and cannot be segmented (false). - Convert
wordDictto aHashSetfor efficient lookups. - Define a recursive helper function
wb(s, wordSet, start, memo). - Base Case: If
startreaches the end of the string (s.length()), it means the entire string has been successfully segmented. Returntrue. - Memoization Check: If
memo[start]is notnull, return its value. - Iterate with an
endindex fromstart + 1tos.length(). - For each
end, check if the substrings.substring(start, end)is in thewordSet. - If it is, make a recursive call for the rest of the string:
wb(s, wordSet, end, memo). - If the recursive call returns
true, it means a valid segmentation is possible. Setmemo[start] = trueand returntrue. - If the loop finishes, no segmentation was found starting from
start. Setmemo[start] = falseand returnfalse.
Walkthrough
We use a memoization table (e.g., an array or a map) to store the results for subproblems. The key to the table is the starting index of the substring, and the value is a boolean indicating whether the substring from that index to the end can be segmented. The recursive function is modified to first check the memoization table. If the result for a given starting index is already computed, it's returned directly. Otherwise, the result is computed, stored in the table, and then returned.
public class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); Boolean[] memo = new Boolean[s.length()]; return wb(s, wordSet, 0, memo); } private boolean wb(String s, Set<String> wordSet, int start, Boolean[] memo) { if (start == s.length()) { return true; } if (memo[start] != null) { return memo[start]; } for (int end = start + 1; end <= s.length(); end++) { if (wordSet.contains(s.substring(start, end)) && wb(s, wordSet, end, memo)) { memo[start] = true; return true; } } memo[start] = false; return false; }}Complexity
Time
O(n^3)
Space
O(n)
Trade-offs
Pros
Significantly more efficient than brute-force recursion.
Avoids TLE for many cases by eliminating redundant computations.
Still maintains a relatively clear, top-down recursive structure.
Cons
The time complexity is
O(n^3)due to the nested loops and substring operations, which can still be slow for very largen.Can lead to
StackOverflowErrorfor very deep recursion, although the constraints ons.lengthmake this unlikely.
This is an iterative approach that builds the solution from the bottom up. We use a DP array, where dp[i] indicates whether the prefix of the string of length i (s.substring(0, i)) can be segmented. The final answer is dp[n], where n is the length of the string.
Algorithm
- Convert
wordDictto aHashSetforO(1)lookups. Also, find the maximum length (maxLen) of a word in the dictionary. - Create a boolean DP array
dpof sizen + 1and initialize all elements tofalse. - Set
dp[0] = trueas the base case. - Iterate
ifrom1ton. Thisirepresents the length of the prefix being considered. - For each
i, iteratejfromi-1down to0. The substring to check iss[j...i-1]. - To optimize, we can stop the inner loop once the length of the substring
(i-j)exceedsmaxLen. So,jgoes fromi-1down tomax(0, i - maxLen). - Inside the inner loop, if
dp[j]istrueandwordSet.contains(s.substring(j, i)), it means we found a valid segmentation for the prefix of lengthi. - Set
dp[i] = trueandbreakthe inner loop to proceed to the nexti. - After the loops complete,
dp[n]holds the result for the entire string.
Walkthrough
We define a boolean array dp of size n + 1. dp[i] is true if the substring s[0...i-1] can be segmented, and false otherwise.
The base case is dp[0] = true, as an empty string can always be considered segmented.
We then iterate from i = 1 to n, calculating dp[i]. To compute dp[i], we look for a split point j (where 0 <= j < i). If dp[j] is true (meaning s[0...j-1] is segmentable) and the remaining part s[j...i-1] is a word in the dictionary, then dp[i] can be set to true.
A key optimization is to only check for words up to the maximum length found in the dictionary. This reduces the number of checks in the inner loop.
public class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); int n = s.length(); int maxLen = 0; for (String word : wordDict) { maxLen = Math.max(maxLen, word.length()); } boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = i - 1; j >= 0 && i - j <= maxLen; j--) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; }}Complexity
Time
O(n * m * m)
Space
O(n + L)
Trade-offs
Pros
Most efficient approach for the given constraints.
Avoids recursion overhead and potential stack overflow issues.
The optimization using
maxLensignificantly improves performance over the naiveO(n^3)DP.
Cons
Can be slightly less intuitive to formulate than the top-down recursive approach for beginners.
Solutions
Solution
public class Solution { public bool WordBreak(string s, IList < string > wordDict) { var words = new HashSet < string > (wordDict); int n = s.Length; var dp = new bool[n + 1]; dp[0] = true; for (int i = 1; i <= n; ++i) { for (int j = 0; j < i; ++j) { if (dp[j] && words.Contains(s.Substring(j, i - j))) { dp[i] = true; break; } } } return dp[n]; }}import java.util.LinkedList ; import java.util.Queue ; import java.util.Set ; public class Word_Break { /* input - 1: "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"] input - 2: "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"] */ public class Solution_dp { public boolean wordBreak ( String s , Set < String > dict ) { if ( s == null || dict == null || dict . size () == 0 ) return false ; int length = s . length (); // since both dfs and bfs not working, try dynamic programming here // construct dp, dp[i] meaning position i-1 can from dict or not boolean [] dp = new boolean [ length + 1 ]; dp [ 0 ] = true ; // @note: initiate for ( int i = 0 ; i < length + 1 ; i ++) { if ( dp [ i ] == false ) { continue ; } else { // if some previous dict word ending at index i-1 for ( String each: dict ) { if ( i + each . length () > length ) continue ; if ( s . substring ( i , i + each . length ()). equals ( each )) { dp [ i + each . length ()] = true ; // i = i + each.length() - 1; // i++ later // break; } } } } return dp [ length ]; } } public class Solution_bfs_over_time { public boolean wordBreak ( String s , Set < String > wordDict ) { if ( s == null || s . length () == 0 || wordDict == null || wordDict . size () == 0 ) { return false ; } // since dfs is not working, now try bfs. all valid word's substring enqueue Queue < String > q = new LinkedList <>(); q . offer ( s ); while (! q . isEmpty ()) { String current = q . poll (); // if (current.length() == 0) { // meaning all previoius matched in dict // return true; // } for ( int i = 0 ; i < current . length (); i ++) { String sub = current . substring ( 0 , i + 1 ); if ( wordDict . contains ( sub )) { if ( s . endsWith ( sub )) { // @note: here is key, I missed it and the last word keeps dequeue and enqueue, infinite looping return true ; } // q.offer(s.substring(i + 1)); // @note: mistake here, should be current.substring(), not s.substring() q . offer ( current . substring ( i + 1 )); } } } return false ; } } public class Solution_dfs_over_time { public boolean wordBreak ( String s , Set < String > wordDict ) { // @note: here is contradictory somehow, maybe a separate helper method would be good // if (s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) { if ( s == null || wordDict == null ) { return false ; } if ( s . length () == 0 ) { return true ; } // substring from index 0 to i, check if in wordDict for ( int i = 0 ; i < s . length (); i ++) { String sub = s . substring ( 0 , i + 1 ); if ( wordDict . contains ( sub )) { boolean isBreakable = wordBreak ( s . substring ( i + 1 ), wordDict ); // just write out logic more clearly if ( isBreakable ) { return true ; } } } return false ; } } } ////// class Solution { public 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 ; 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 ; break ; } } } return dp [ n ]; } }class Solution: def wordBreak(self, s: str, wordDict: List[str]) -> bool: words = set(wordDict) n = len(s) # dp[j] meaining s from 0 to index=i-1~ is breakable dp = [ True ] + [ False ] * n # so actually size is n+1 for i in range ( 1 , n + 1 ): dp [ i ] = any ( ( dp [ j ] and s [ j : i ] in words ) for j in range ( i ) ) return dp [ n ] ############# class Solution : def wordBreak ( self , s : str , wordDict : Set [ str ]) -> bool : if not s or not wordDict : return False length = len ( s ) # construct dp, dp[i] meaning position i-1 can from dict or not dp [ - 1 ] meaning at last - index plus 1 , checking up to last - index dp = [ False ] * ( length + 1 ) dp [ 0 ] = True # initiate for i in range ( length + 1 ): if not dp [ i ]: continue for word in wordDict : if i + len ( word ) > length : continue if s [ i : i + len ( word )] == word : dp [ i + len ( word )] = True return dp [ length ] ############# class Solution : def wordBreak ( self , s : str , wordDict : List [ str ]) -> bool : words = set ( wordDict ) n = len ( s ) dp = [ False ] * ( n + 1 ) dp [ 0 ] = True # i'th char in string, is good for j in range ( 1 , n + 1 ): for i in range ( j ): # starting at 0, includng dp[0] if dp [ i ] and s [ i : j ] in words : dp [ j ] = True # j is exclusive, meaining True until index i-1 break return dp [ - 1 ] ############# class Trie : def __init__ ( self ): self . children = [ None ] * 26 self . is_end = False def insert ( self , w ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : node . children [ idx ] = Trie () node = node . children [ idx ] node . is_end = True def search ( self , w ): node = self for c in w : idx = ord ( c ) - ord ( 'a' ) if node . children [ idx ] is None : return False node = node . children [ idx ] return node . is_end class Solution : def wordBreak ( self , s : str , wordDict : List [ str ]) -> bool : # https://docs.python.org/3/library/functools.html#functools.cache # creating a thin wrapper around a dictionary lookup for the function arguments @ cache def dfs ( s ): return not s or any ( trie . search ( s [: i ]) and dfs ( s [ i :]) for i in range ( 1 , len ( s ) + 1 )) trie = Trie () for w in wordDict : trie . insert ( w ) return dfs ( s ) ############# class Solution ( object ): def wordBreak ( self , s , wordDict ): """ :type s: str :type wordDict: Set[str] :rtype: bool """ queue = [ 0 ] ls = len ( s ) lenList = [ l for l in set ( map ( len , wordDict ))] visited = [ 0 for _ in range ( 0 , ls + 1 )] while queue : start = queue . pop ( 0 ) for l in lenList : if s [ start : start + l ] in wordDict : if start + l == ls : return True if visited [ start + l ] == 0 : queue . append ( start + l ) visited [ start + l ] = 1 return False// OJ: https://leetcode.com/problems/word-break/ // Time: O(S^3) // Space: O(S + W) class Solution { public: bool wordBreak ( string s , vector < string >& dict ) { unordered_set < string > st ( begin ( dict ), end ( dict )); int N = s . size (); vector < bool > dp ( N + 1 ); dp [ 0 ] = true ; for ( int i = 1 ; i <= N ; ++ i ) { for ( int j = 0 ; j < i && ! dp [ i ]; ++ j ) { dp [ i ] = dp [ j ] && st . count ( s . substr ( j , i - j )); } } return dp [ N ]; } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.