# Word Break **Difficulty:** MEDIUM [External](https://leetcode.com/problems/word-break) Canonical: https://scaleengineer.com/dsa/problems/word-break **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization) **Data structures:** Array, Hash Table, String, Trie **Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [IBM](https://scaleengineer.com/companies/ibm), [Intuit](https://scaleengineer.com/companies/intuit), [Nutanix](https://scaleengineer.com/companies/nutanix), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [SAP](https://scaleengineer.com/companies/sap), [Snowflake](https://scaleengineer.com/companies/snowflake), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Grammarly](https://scaleengineer.com/companies/grammarly), [MongoDB](https://scaleengineer.com/companies/mongodb), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [Nordstrom](https://scaleengineer.com/companies/nordstrom), [Netskope](https://scaleengineer.com/companies/netskope), [CureFit](https://scaleengineer.com/companies/curefit), [Block](https://scaleengineer.com/companies/block), [Cleartrip](https://scaleengineer.com/companies/cleartrip), [Otter.ai](https://scaleengineer.com/companies/otter.ai) --- ## Problem 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 <= 300` * `1 <= wordDict.length <= 1000` * `1 <= wordDict[i].length <= 20` * `s` and `wordDict[i]` consist of only lowercase English letters. * All the strings of `wordDict` are **unique**. # Approaches ## Brute-Force Recursion 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. **Time:** O(2^n) · **Space:** O(n) **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. ### Explanation 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`. ```java public class Solution { public boolean wordBreak(String s, List wordDict) { Set wordSet = new HashSet<>(wordDict); return wb(s, wordSet); } private boolean wb(String s, Set 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; } } ``` ### Algorithm - Create a `HashSet` from the `wordDict` for `O(1)` average time lookups. - Define a recursive helper function `wb(s, wordSet)`. - **Base Case**: If `s` is empty, return `true`. - Iterate with an index `i` from 1 to `s.length()`. - In each iteration, get the prefix `s.substring(0, i)`. - Check if the `wordSet` contains this prefix. - If it does, recursively call `wb` with the suffix `s.substring(i)`. - If the recursive call returns `true`, return `true` from the current function. - If the loop completes without returning, it means no valid segmentation was found starting with any prefix. Return `false`. ## Recursion with Memoization (Top-Down DP) 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. **Time:** O(n^3) · **Space:** O(n) **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 large `n`.; Can lead to `StackOverflowError` for very deep recursion, although the constraints on `s.length` make this unlikely. ### Explanation 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. ```java public class Solution { public boolean wordBreak(String s, List wordDict) { Set wordSet = new HashSet<>(wordDict); Boolean[] memo = new Boolean[s.length()]; return wb(s, wordSet, 0, memo); } private boolean wb(String s, Set 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; } } ``` ### Algorithm - Create a memoization array, `memo`, of size `s.length()`. We can use a `Boolean` array initialized to `null`s to represent three states: not computed (`null`), can be segmented (`true`), and cannot be segmented (`false`). - Convert `wordDict` to a `HashSet` for efficient lookups. - Define a recursive helper function `wb(s, wordSet, start, memo)`. - **Base Case**: If `start` reaches the end of the string (`s.length()`), it means the entire string has been successfully segmented. Return `true`. - **Memoization Check**: If `memo[start]` is not `null`, return its value. - Iterate with an `end` index from `start + 1` to `s.length()`. - For each `end`, check if the substring `s.substring(start, end)` is in the `wordSet`. - 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. Set `memo[start] = true` and return `true`. - If the loop finishes, no segmentation was found starting from `start`. Set `memo[start] = false` and return `false`. ## Dynamic Programming (Bottom-Up) 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. **Time:** O(n * m * m) · **Space:** O(n + L) **Pros:** Most efficient approach for the given constraints.; Avoids recursion overhead and potential stack overflow issues.; The optimization using `maxLen` significantly improves performance over the naive `O(n^3)` DP. **Cons:** Can be slightly less intuitive to formulate than the top-down recursive approach for beginners. ### Explanation 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. ```java public class Solution { public boolean wordBreak(String s, List wordDict) { Set 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]; } } ``` ### Algorithm - Convert `wordDict` to a `HashSet` for `O(1)` lookups. Also, find the maximum length (`maxLen`) of a word in the dictionary. - Create a boolean DP array `dp` of size `n + 1` and initialize all elements to `false`. - Set `dp[0] = true` as the base case. - Iterate `i` from `1` to `n`. This `i` represents the length of the prefix being considered. - For each `i`, iterate `j` from `i-1` down to `0`. The substring to check is `s[j...i-1]`. - To optimize, we can stop the inner loop once the length of the substring `(i-j)` exceeds `maxLen`. So, `j` goes from `i-1` down to `max(0, i - maxLen)`. - Inside the inner loop, if `dp[j]` is `true` and `wordSet.contains(s.substring(j, i))`, it means we found a valid segmentation for the prefix of length `i`. - Set `dp[i] = true` and `break` the inner loop to proceed to the next `i`. - After the loops complete, `dp[n]` holds the result for the entire string. # Solutions ### CSharp ```csharp 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]; } } ``` ### Java ```java 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 ]; } } ``` ### Python ```python 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 ``` ### CPP ```cpp // 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 ]; } }; ```