Minimum Word Break
Given a string s, break s such that every substring of the partition can be found in the dictionary. Return the minimum break needed.
Examples:
Given a dictionary ["Cat", "Mat", "Ca",
"tM", "at", "C", "Dog", "og", "Do"]
Input : Pattern "CatMat"
Output : 1
Explanation: we can break the sentences
in three ways, as follows:
CatMat = [ Cat Mat ] break 1
CatMat = [ Ca tM at ] break 2
CatMat = [ C at Mat ] break 2 so the
output is: 1
Input : Dogcat
Output : 1
Asked in: Facebook
Solution of this problem is based on the WordBreak Trie solution and level ordered graph. We start traversing given pattern and start finding a character of pattern in a trie. If we reach a node(leaf) of a trie from where we can traverse a new word of a trie(dictionary), we increment level by one and call search function for rest of the pattern character in a trie. In the end, we return minimum Break.
MinBreak(Trie, key, level, start = 0 )
.... If start == key.length()
...update min_break
for i = start to keylength
....If we found a leaf node in trie
MinBreak( Trie, key, level+1, i )
Below is the implementation of above idea
C++
Java
Python3
C#
<div id= "highlighter_340365" class = "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class = "code" ><div class = "container" ><div class = "line number1 index0 alt2" ><code class = "comments" > // C# program to find minimum breaks needed </code></div><div class="line number2 index1 alt1"><code class="comments">// to break a string in dictionary words.</code></div><div class="line number3 index2 alt2"><code class="keyword">using</code> <code class="plain">System; </code></div><div class="line number4 index3 alt1"> </div><div class="line number5 index4 alt2"><code class="keyword">class</code> <code class="plain">Trie</code></div><div class="line number6 index5 alt1"><code class="plain">{ </code></div><div class="line number7 index6 alt2"> </div><div class="line number8 index7 alt1"><code class="undefined spaces"> </code><code class="plain">TrieNode root = </code><code class="keyword">new</code> <code class="plain">TrieNode(); </code></div><div class="line number9 index8 alt2"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">minWordBreak = </code><code class="keyword">int</code><code class="plain">.MaxValue ; </code></div><div class="line number10 index9 alt1"> </div><div class="line number11 index10 alt2"><code class="undefined spaces"> </code><code class="comments">// Trie node </code></div><div class="line number12 index11 alt1"><code class="undefined spaces"> </code><code class="keyword">public</code> <code class="keyword">class</code> <code class="plain">TrieNode </code></div><div class="line number13 index12 alt2"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number14 index13 alt1"><code class="undefined spaces"> </code><code class="keyword">public</code> <code class="keyword">bool</code> <code class="plain">endOfTree; </code></div><div class="line number15 index14 alt2"><code class="undefined spaces"> </code><code class="keyword">public</code> <code class="plain">TrieNode []children = </code><code class="keyword">new</code> <code class="plain">TrieNode[26]; </code></div><div class="line number16 index15 alt1"><code class="undefined spaces"> </code><code class="keyword">public</code> <code class="plain">TrieNode()</code></div><div class="line number17 index16 alt2"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number18 index17 alt1"><code class="undefined spaces"> </code><code class="plain">endOfTree = </code><code class="keyword">false</code><code class="plain">; </code></div><div class="line number19 index18 alt2"><code class="undefined spaces"> </code><code class="keyword">for</code><code class="plain">(</code><code class="keyword">int</code> <code class="plain">i = 0; i < 26; i++)</code></div><div class="line number20 index19 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number21 index20 alt2"><code class="undefined spaces"> </code><code class="plain">children[i] = </code><code class="keyword">null</code><code class="plain">; </code></div><div class="line number22 index21 alt1"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number23 index22 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number24 index23 alt1"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number25 index24 alt2"> </div><div class="line number26 index25 alt1"><code class="undefined spaces"> </code><code class="comments">// If not present, inserts a key </code></div><div class="line number27 index26 alt2"><code class="undefined spaces"> </code><code class="comments">// into the trie If the key is the </code></div><div class="line number28 index27 alt1"><code class="undefined spaces"> </code><code class="comments">// prefix of trie node, just marks leaf node </code></div><div class="line number29 index28 alt2"><code class="undefined spaces"> </code><code class="keyword">void</code> <code class="plain">insert(String key)</code></div><div class="line number30 index29 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number31 index30 alt2"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">length = key.Length; </code></div><div class="line number32 index31 alt1"> </div><div class="line number33 index32 alt2"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">index; </code></div><div class="line number34 index33 alt1"> </div><div class="line number35 index34 alt2"><code class="undefined spaces"> </code><code class="plain">TrieNode pcrawl = root; </code></div><div class="line number36 index35 alt1"> </div><div class="line number37 index36 alt2"><code class="undefined spaces"> </code><code class="keyword">for</code><code class="plain">(</code><code class="keyword">int</code> <code class="plain">i = 0; i < length; i++) </code></div><div class="line number38 index37 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number39 index38 alt2"><code class="undefined spaces"> </code><code class="plain">index = key[i]- </code><code class="string">'a'</code><code class="plain">; </code></div><div class="line number40 index39 alt1"> </div><div class="line number41 index40 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code><code class="plain">(pcrawl.children[index] == </code><code class="keyword">null</code><code class="plain">) </code></div><div class="line number42 index41 alt1"><code class="undefined spaces"> </code><code class="plain">pcrawl.children[index] = </code><code class="keyword">new</code> <code class="plain">TrieNode(); </code></div><div class="line number43 index42 alt2"> </div><div class="line number44 index43 alt1"><code class="undefined spaces"> </code><code class="plain">pcrawl = pcrawl.children[index]; </code></div><div class="line number45 index44 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number46 index45 alt1"><code class="undefined spaces"> </code> </div><div class="line number47 index46 alt2"><code class="undefined spaces"> </code><code class="comments">// mark last node as leaf </code></div><div class="line number48 index47 alt1"><code class="undefined spaces"> </code><code class="plain">pcrawl.endOfTree = </code><code class="keyword">true</code><code class="plain">; </code></div><div class="line number49 index48 alt2"> </div><div class="line number50 index49 alt1"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number51 index50 alt2"> </div><div class="line number52 index51 alt1"><code class="undefined spaces"> </code><code class="comments">// function break the string into minimum cut </code></div><div class="line number53 index52 alt2"><code class="undefined spaces"> </code><code class="comments">// such the every substring after breaking </code></div><div class="line number54 index53 alt1"><code class="undefined spaces"> </code><code class="comments">// in the dictionary. </code></div><div class="line number55 index54 alt2"><code class="undefined spaces"> </code><code class="keyword">void</code> <code class="plain">minWordBreaks(String key) </code></div><div class="line number56 index55 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number57 index56 alt2"><code class="undefined spaces"> </code><code class="plain">minWordBreak = </code><code class="keyword">int</code><code class="plain">.MaxValue; </code></div><div class="line number58 index57 alt1"><code class="undefined spaces"> </code><code class="plain">minWordBreakUtil(root, key, 0, </code><code class="keyword">int</code><code class="plain">.MaxValue, 0); </code></div><div class="line number59 index58 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number60 index59 alt1"><code class="undefined spaces"> </code> </div><div class="line number61 index60 alt2"><code class="undefined spaces"> </code><code class="keyword">void</code> <code class="plain">minWordBreakUtil(TrieNode node, String key, </code></div><div class="line number62 index61 alt1"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">start, </code><code class="keyword">int</code> <code class="plain">min_Break, </code><code class="keyword">int</code> <code class="plain">level) </code></div><div class="line number63 index62 alt2"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number64 index63 alt1"><code class="undefined spaces"> </code><code class="plain">TrieNode pCrawl = node; </code></div><div class="line number65 index64 alt2"> </div><div class="line number66 index65 alt1"><code class="undefined spaces"> </code><code class="comments">// base case, update minimum Break </code></div><div class="line number67 index66 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(start == key.Length) </code></div><div class="line number68 index67 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number69 index68 alt2"><code class="undefined spaces"> </code><code class="plain">min_Break = Math.Min(min_Break, level - 1); </code></div><div class="line number70 index69 alt1"><code class="undefined spaces"> </code><code class="keyword">if</code><code class="plain">(min_Break < minWordBreak)</code></div><div class="line number71 index70 alt2"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number72 index71 alt1"><code class="undefined spaces"> </code><code class="plain">minWordBreak = min_Break; </code></div><div class="line number73 index72 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number74 index73 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code><code class="plain">; </code></div><div class="line number75 index74 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number76 index75 alt1"> </div><div class="line number77 index76 alt2"><code class="undefined spaces"> </code><code class="comments">// traverse given key(pattern) </code></div><div class="line number78 index77 alt1"><code class="undefined spaces"> </code><code class="keyword">for</code> <code class="plain">(</code><code class="keyword">int</code> <code class="plain">i = start; i < key.Length; i++) </code></div><div class="line number79 index78 alt2"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number80 index79 alt1"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">index = key[i] - </code><code class="string">'a'</code><code class="plain">; </code></div><div class="line number81 index80 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(pCrawl.children[index]==</code><code class="keyword">null</code><code class="plain">) </code></div><div class="line number82 index81 alt1"><code class="undefined spaces"> </code><code class="keyword">return</code><code class="plain">; </code></div><div class="line number83 index82 alt2"> </div><div class="line number84 index83 alt1"><code class="undefined spaces"> </code><code class="comments">// if we find a condition were we can </code></div><div class="line number85 index84 alt2"><code class="undefined spaces"> </code><code class="comments">// move to the next word in a trie </code></div><div class="line number86 index85 alt1"><code class="undefined spaces"> </code><code class="comments">// dictionary </code></div><div class="line number87 index86 alt2"><code class="undefined spaces"> </code><code class="keyword">if</code> <code class="plain">(pCrawl.children[index].endOfTree) </code></div><div class="line number88 index87 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number89 index88 alt2"><code class="undefined spaces"> </code><code class="plain">minWordBreakUtil(root, key, i + 1, </code></div><div class="line number90 index89 alt1"><code class="undefined spaces"> </code><code class="plain">min_Break, level + 1); </code></div><div class="line number91 index90 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number92 index91 alt1"><code class="undefined spaces"> </code><code class="plain">pCrawl = pCrawl.children[index]; </code></div><div class="line number93 index92 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number94 index93 alt1"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number95 index94 alt2"> </div><div class="line number96 index95 alt1"><code class="undefined spaces"> </code><code class="comments">// Driver code </code></div><div class="line number97 index96 alt2"><code class="undefined spaces"> </code><code class="keyword">public</code> <code class="keyword">static</code> <code class="keyword">void</code> <code class="plain">Main(String[] args) </code></div><div class="line number98 index97 alt1"><code class="undefined spaces"> </code><code class="plain">{ </code></div><div class="line number99 index98 alt2"><code class="undefined spaces"> </code><code class="plain">String []keys = {</code><code class="string">"cat"</code><code class="plain">, </code><code class="string">"mat"</code><code class="plain">, </code><code class="string">"ca"</code><code class="plain">, </code><code class="string">"ma"</code><code class="plain">, </code></div><div class="line number100 index99 alt1"><code class="undefined spaces"> </code><code class="string">"at"</code><code class="plain">, </code><code class="string">"c"</code><code class="plain">, </code><code class="string">"dog"</code><code class="plain">, </code><code class="string">"og"</code><code class="plain">, </code><code class="string">"do"</code> <code class="plain">}; </code></div><div class="line number101 index100 alt2"> </div><div class="line number102 index101 alt1"><code class="undefined spaces"> </code><code class="plain">Trie trie = </code><code class="keyword">new</code> <code class="plain">Trie(); </code></div><div class="line number103 index102 alt2"> </div><div class="line number104 index103 alt1"><code class="undefined spaces"> </code><code class="comments">// Construct trie </code></div><div class="line number105 index104 alt2"><code class="undefined spaces"> </code><code class="keyword">int</code> <code class="plain">i; </code></div><div class="line number106 index105 alt1"><code class="undefined spaces"> </code><code class="keyword">for</code> <code class="plain">(i = 0; i < keys.Length ; i++) </code></div><div class="line number107 index106 alt2"><code class="undefined spaces"> </code><code class="plain">trie.insert(keys[i]); </code></div><div class="line number108 index107 alt1"><code class="undefined spaces"> </code> </div><div class="line number109 index108 alt2"><code class="undefined spaces"> </code><code class="plain">trie.minWordBreaks(</code><code class="string">"catmatat"</code><code class="plain">); </code></div><div class="line number110 index109 alt1"><code class="undefined spaces"> </code><code class="plain">Console.WriteLine(trie.minWordBreak); </code></div><div class="line number111 index110 alt2"><code class="undefined spaces"> </code><code class="plain">} </code></div><div class="line number112 index111 alt1"><code class="plain">} </code></div><div class="line number113 index112 alt2"> </div><div class="line number114 index113 alt1"><code class="comments">// This code is contributed by 29AjayKumar</code></div></div></td></tr></tbody></table></div> |
Javascript
<script> // JavaScript program to find minimum breaks needed // to break a string in dictionary words. class TrieNode { constructor() { this .endOfTree= false ; this .children= new Array(26); for (let i=0;i<26;i++) this .children[i]= null ; } } let root = new TrieNode(); let minWordBreak = Number.MAX_VALUE; // If not present, inserts a key into the trie // If the key is the prefix of trie node, just // marks leaf node function insert(key) { let length = key.length; let index; let pcrawl = root; for (let i = 0; i < length; i++) { index = key[i].charAt(0)- 'a' .charAt(0); if (pcrawl.children[index] == null ) pcrawl.children[index] = new TrieNode(); pcrawl = pcrawl.children[index]; } // mark last node as leaf pcrawl.endOfTree = true ; } // function break the string into minimum cut // such the every substring after breaking // in the dictionary. function _minWordBreak(key) { minWordBreak = Number.MAX_VALUE; minWordBreakUtil(root, key, 0, Number.MAX_VALUE, 0); } function minWordBreakUtil(node,key,start,min_Break,level) { let pCrawl = node; // base case, update minimum Break if (start == key.length) { min_Break = Math.min(min_Break, level - 1); if (min_Break<minWordBreak){ minWordBreak = min_Break; } return ; } // traverse given key(pattern) for (let i = start; i < key.length; i++) { let index = key[i].charAt(0) - 'a' .charAt(0); if (pCrawl.children[index]== null ) return ; // if we find a condition were we can // move to the next word in a trie // dictionary if (pCrawl.children[index].endOfTree) { minWordBreakUtil(root, key, i + 1, min_Break, level + 1); } pCrawl = pCrawl.children[index]; } } // Driver code let keys=[ "cat" , "mat" , "ca" , "ma" , "at" , "c" , "dog" , "og" , "do" ]; let i; for (i = 0; i < keys.length ; i++) insert(keys[i]); _minWordBreak( "catmatat" ); document.write(minWordBreak); // This code is contributed by rag2127 </script> |
2
Time Complexity: O(n*n*L) where n is the length of the input string and L is the maximum length of word in the dictionary.
Auxiliary Space: O(ALPHABET_SIZE^L+n*L)
Approach 2: Using Dynamic Programming
- We maintain an array dp where dp[i] represents the minimum number of breaks needed to break the substring s[0…i-1] into dictionary words.
- We initialize dp[0] = 0 since the empty string can be broken into zero words.
- For each position i in the string, we iterate over all dictionary words and check if the substring ending at position i matches the current dictionary word.
- If it does, we update dp[i] to be the minimum of dp[i] and dp[i – len] + 1, where len is the length of the current dictionary word.
- Finally, we return dp[n] – 1, where n is the length of the input string, since the number of breaks needed is one less than the number of words.
C++
< div id= "highlighter_960148" class = "syntaxhighlighter nogutter " ><table border= "0" cellpadding= "0" cellspacing= "0" ><tbody><tr><td class = "code" >< div class = "container" >< div class = "line number1 index0 alt2" ><code class = "preprocessor" >#include <bits/stdc++.h></code></ div >< div class = "line number2 index1 alt1" ><code class = "keyword bold" > using </code> <code class = "keyword bold" > namespace </code> <code class = "plain" >std;</code></ div >< div class = "line number3 index2 alt2" > </ div >< div class = "line number4 index3 alt1" ><code class = "keyword bold" > const </code> <code class = "color1 bold" > int </code> <code class = "plain" >INF = 1e9;</code></ div >< div class = "line number5 index4 alt2" > </ div >< div class = "line number6 index5 alt1" ><code class = "color1 bold" > int </code> <code class = "plain" >minWordBreak(string s, vector<string>& dict) {</code></ div >< div class = "line number7 index6 alt2" ><code class = "undefined spaces" > </code><code class = "color1 bold" > int </code> <code class = "plain" >n = s.length();</code></ div >< div class = "line number8 index7 alt1" ><code class = "undefined spaces" > </code><code class = "plain" >vector<</code><code class = "color1 bold" > int </code><code class = "plain" >> dp(n + 1, INF);</code></ div >< div class = "line number9 index8 alt2" ><code class = "undefined spaces" > </code><code class = "plain" >dp[0] = 0;</code></ div >< div class = "line number10 index9 alt1" > </ div >< div class = "line number11 index10 alt2" ><code class = "undefined spaces" > </code><code class = "keyword bold" > for </code> <code class = "plain" >(</code><code class = "color1 bold" > int </code> <code class = "plain" >i = 1; i <= n; i++) {</code></ div >< div class = "line number12 index11 alt1" ><code class = "undefined spaces" > </code><code class = "keyword bold" > for </code> <code class = "plain" >(string word : dict) {</code></ div >< div class = "line number13 index12 alt2" ><code class = "undefined spaces" > </code><code class = "color1 bold" > int </code> <code class = "plain" >len = word.length();</code></ div >< div class = "line number14 index13 alt1" ><code class = "undefined spaces" > </code><code class = "keyword bold" > if </code> <code class = "plain" >(i >= len && s.substr(i - len, len) == word) {</code></ div >< div class = "line number15 index14 alt2" ><code class = "undefined spaces" > </code><code class = "plain" >dp[i] = min(dp[i], dp[i - len] + 1);</code></ div >< div class = "line number16 index15 alt1" ><code class = "undefined spaces" > </code><code class = "plain" >}</code></ div >< div class = "line number17 index16 alt2" ><code class = "undefined spaces" > </code><code class = "plain" >}</code></ div >< div class = "line number18 index17 alt1" ><code class = "undefined spaces" > </code><code class = "plain" >}</code></ div >< div class = "line number19 index18 alt2" > </ div >< div class = "line number20 index19 alt1" ><code class = "undefined spaces" > </code><code class = "keyword bold" > return </code> <code class = "plain" >dp[n] - 1;</code></ div >< div class = "line number21 index20 alt2" ><code class = "plain" >}</code></ div >< div class = "line number22 index21 alt1" > </ div >< div class = "line number23 index22 alt2" ><code class = "color1 bold" > int </code> <code class = "plain" >main() {</code></ div >< div class = "line number24 index23 alt1" ><code class = "undefined spaces" > </code><code class = "plain" >vector<string> dict = {</code><code class = "string" > "Cat" </code><code class = "plain" >, </code><code class = "string" > "Mat" </code><code class = "plain" >, </code><code class = "string" > "Ca" </code><code class = "plain" >, </code><code class = "string" > "Ma" </code><code class = "plain" >, </code><code class = "string" > "at" </code><code class = "plain" >, </code><code class = "string" > "C" </code><code class = "plain" >, </code><code class = "string" > "Dog" </code><code class = "plain" >, </code><code class = "string" > "og" </code><code class = "plain" >, </code><code class = "string" > "Do" </code><code class = "plain" >};</code></ div >< div class = "line number25 index24 alt2" ><code class = "undefined spaces" > </code><code class = "plain" >string s = </code><code class = "string" > "CatMatat" </code><code class = "plain" >;</code></ div >< div class = "line number26 index25 alt1" ><code class = "undefined spaces" > </code><code class = "plain" >cout << minWordBreak(s, dict) << endl;</code></ div >< div class = "line number27 index26 alt2" ><code class = "undefined spaces" > </code><code class = "keyword bold" > return </code> <code class = "plain" >0;</code></ div >< div class = "line number28 index27 alt1" ><code class = "plain" >}</code></ div ></ div ></td></tr></tbody></table></ div > |
Java
Python3
C#
Javascript
2
Note that this code has a time complexity of O(n*m), where n is the length of the input string and m is the size of the dictionary. This is because we iterate over all positions in the string and for each position, we iterate over all words in the dictionary.
Contact Us