{"id":3913,"date":"2021-11-18T14:55:38","date_gmt":"2021-11-18T09:25:38","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=3913"},"modified":"2022-06-15T11:47:10","modified_gmt":"2022-06-15T06:17:10","slug":"word-break-problem","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/word-break-problem\/","title":{"rendered":"Word Break Problem (With Solution)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given a string <strong>s<\/strong> and a dictionary of strings. The task is to check whether the given string <strong>S<\/strong> can be broken into individual words from the dictionary.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong><strong><br><\/strong><strong>s<\/strong> = &#8220;applepenapple&#8221;<br><strong>words<\/strong> = [&#8220;apple&#8221;, &#8220;pen&#8221;]; <strong>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/strong><\/p>\n\n\n\n<p><br><strong>Output:<\/strong> True<br><strong>Explanation:<br><\/strong>The string \u201c<strong>applepenapple<\/strong>\u201d can be broken into \u201capple pen apple\u201d<strong><br><br><\/strong><br><strong>Input: <br>s<\/strong> = &#8220;catsandog&#8221;<br><strong>words<\/strong> = [&#8220;cats&#8221;, &#8220;dog&#8221;, &#8220;sand&#8221;, &#8220;and&#8221;, &#8220;cat&#8221;]<strong>&nbsp; &nbsp; &nbsp; &nbsp;<\/strong><br><strong>Output:<\/strong> False<br><\/p>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>The most basic approach to solve this problem is to simply use recursion and backtracking. The key idea is to check every possible prefix of the given string in the dictionary of words. If the prefix is found in the dictionary of words, run the recursive function for the rest of the string and at any point if the whole string is found, simply return True.<\/p>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool wordBreak(string s, vector &lt; string > &amp; wordDict) {\n  set &lt; string > word_set(wordDict.begin(), wordDict.end());\n  return wordBreakRecur(s, word_set, 0);\n}\n \nbool wordBreakRecur(string &amp; s, set &lt; string > &amp; word_set, int start) {\n  if (start == s.length()) {\n    return true;\n  }\n  for (int end = start + 1; end &lt;= s.length(); end++) {\n    if (word_set.find(s.substr(start, end - start)) != word_set.end() and wordBreakRecur(s, word_set, end)) {\n      return true;\n    }\n  }\n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> public boolean wordBreak(String s, List &lt; String > wordDict) {\n  return wordBreakRecur(s, new HashSet &lt; > (wordDict), 0);\n}\n \nprivate boolean wordBreakRecur(String s, Set &lt; String > wordDict, int start) {\n  if (start == s.length()) {\n    return true;\n  }\n  for (int end = start + 1; end &lt;= s.length(); end++) {\n    if (wordDict.contains(s.substring(start, end)) &amp;&amp; wordBreakRecur(s, wordDict, end)) {\n      return true;\n    }\n  }\n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def wordBreak(self, s, wordDict: List[str]) -> bool:\n    def wordBreakRecur(s: str, word_dict: Set[str], start: int):\n        if start == len(s):\n            return True\n        for end in range(start + 1, len(s) + 1):\n            if s[start:end] in word_dict and wordBreakRecur(s, word_dict, end):\n                return True\n        return False\n \n    return wordBreakRecur(s, set(wordDict), 0)<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(2^N), where N is the length of the string S.<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N), for the recursive stack.<\/p>\n\n\n\n<h2 id=\"approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/h2>\n\n\n\n<p>In the previous approach, if you observe carefully, there were many overlapping subproblems which we were calculating again and again.<\/p>\n\n\n\n<p>For example :<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"806\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"partial recursion tree\"  class=\"wp-image-3987 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-1024x806.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-1024x806.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-300x236.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-768x605.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-380x299.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-550x433.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-800x630.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1-1160x913.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/partial-recursion-tree-1.png 1369w\" ><\/figure>\n\n\n\n<p>To avoid repetitive calculations, the idea is to use <strong><a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\">Dynamic Programming<\/a> <\/strong>to solve the problem.<\/p>\n\n\n\n<p>The intuition behind this approach is that the given problem (s) can be divided into subproblems s1 and s2. If these subproblems individually satisfy the required conditions, the complete problem, s also satisfies the same. e.g. &#8220;catsanddog&#8221; can be split into two substrings &#8220;catsand&#8221;, &#8220;dog&#8221;. The subproblem &#8220;catsand&#8221; can be further divided into &#8220;cats&#8221;,&#8221;and&#8221;, which individually are a part of the dictionary making &#8220;catsand&#8221; satisfy the condition. Going further backwards, &#8220;catsand&#8221;, &#8220;dog&#8221; also satisfy the required criteria individually leading to the complete string &#8220;catsanddog&#8221; also to satisfy the criteria.<\/p>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create a <strong>1D<\/strong> <strong>dp <\/strong>array of size <strong>N + 1<\/strong>, where N is the size of S.<\/li><li>Consider two pointers <strong>i<\/strong> and <strong>j<\/strong>, where <strong>i<\/strong> refers the starting of the substring and <strong>j<\/strong> represents the ending of the substring.<\/li><li>Run two nested loop, <strong>i = 0<\/strong> till<strong> N + 1<\/strong> and <strong>j = 0<\/strong> to <strong>j = i<\/strong>:<ul><li>Check if <strong>dp[j] &gt; 0<\/strong> and the dictionary of words contains the substring, then mark <strong>dp[i] = True<\/strong> and break.<\/li><\/ul><\/li><li>Return <strong>dp[N] &gt; 0<\/strong><\/li><\/ul>\n\n\n\n<p><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool wordBreak(string s, vector &lt; string > &amp; wordDict) {\n  set &lt; string > word_set(wordDict.begin(), wordDict.end());\n  vector &lt; bool > dp(s.length() + 1);\n  dp[0] = true;\n \n  for (int i = 1; i &lt;= s.length(); i++) {\n    for (int j = 0; j &lt; i; j++) {\n      if (dp[j] and word_set.find(s.substr(j, i - j)) != word_set.end()) {\n        dp[i] = true;\n        break;\n      }\n    }\n  }\n  return dp[s.length()];\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public boolean wordBreak(String s, List &lt; String > wordDict) {\n  Set &lt; String > wordDictSet = new HashSet &lt; > (wordDict);\n  boolean[] dp = new boolean[s.length() + 1];\n  dp[0] = true;\n  for (int i = 1; i &lt;= s.length(); i++) {\n    for (int j = 0; j &lt; i; j++) {\n      if (dp[j] &amp;&amp; wordDictSet.contains(s.substring(j, i))) {\n        dp[i] = true;\n        break;\n      }\n    }\n  }\n  return dp[s.length()];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def wordBreak(self, s: str, wordDict: List[str]) -> bool:\n    word_set = set(wordDict)\n    dp = [False] * (len(s) + 1)\n    dp[0] = True\n \n    for i in range(1, len(s) + 1):\n        for j in range(i):\n            if dp[j] and s[j:i] in word_set:\n                dp[i] = True\n                break\n    return dp[len(s)]<\/pre>\n\n\n\n<p><strong>Time Complexity: <\/strong>O(N^3), where N is the length of the string S<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N), since dp array is used.<\/p>\n\n\n\n<p><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/word-break\/\" target=\"_blank\" rel=\"noreferrer noopener\">Word Break<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What is the time and space complexity of the dynamic programming approach?<br><\/strong>The time and space complexity of the dynamic programming approach is O(N^3) and O(N), where N is the length of the given string.<br><strong><br><\/strong><\/li><li><strong>How can you calculate the number of different possible words that can be constructed from the given string?<br><\/strong>Following the dynamic programming approach discussed above, instead of making dp[i] = true, add dp[[j &#8211; 1] with dp[i] for j &gt; 0. At the end, return dp[N].<\/li><\/ul>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"Given a string s and a dictionary of strings. The task is to check whether the given string&hellip;\n","protected":false},"author":5,"featured_media":3986,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[586],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3913"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=3913"}],"version-history":[{"count":6,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3913\/revisions"}],"predecessor-version":[{"id":9806,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/3913\/revisions\/9806"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3986"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=3913"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=3913"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=3913"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}