{"id":2104,"date":"2024-03-03T13:00:00","date_gmt":"2024-03-03T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2104"},"modified":"2024-03-04T06:37:05","modified_gmt":"2024-03-04T06:37:05","slug":"word-break-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/word-break-problem\/","title":{"rendered":"Word Break Problem Solved (C++, Java, Python)"},"content":{"rendered":"\n

Recursion is an amazing way to solve many coding problems, but sometimes we repeatedly solve the same thing we have already solved. This can be reduced with the help of dynamic programming<\/a>. In this article, we will discuss the popular programming problem called the \u201cWord Break\u201d and get it using dynamic programming.\u00a0<\/p>\n\n\n\n

What is the Word Break Problem?<\/strong><\/h2>\n\n\n\n

In the Word Break problem, you are given a string and an array containing words that lie in a dictionary. We have to find if we can break the string into substrings such that each substring lies in the dictionary.<\/strong> Note that the same word may be used for more than one substring.<\/p>\n\n\n\n

Let\u2019s understand this with an example:<\/p>\n\n\n\n

\"Example<\/figure>\n\n\n\n

The array given to you is<\/p>\n\n\n\n

\"Example<\/figure>\n\n\n\n
\"Example<\/figure>\n\n\n\n

The simple way to get the answer is by storing the elements of an array in the hash map<\/a>. After that we will recursively check for the substring if it lies in the hashmap check for the next substring. If all the substring lies in the hash map return true. Otherwise, return false.<\/p>\n\n\n\n

Here is how to do it:<\/p>\n\n\n\n

    \n
  1. First store elements of the array into the hash map.<\/li>\n\n\n\n
  2. Now create a function that has parameters start index, end index, hash map, and the string.<\/li>\n\n\n\n
  3. Now call the function with a starting index of 0 and an ending index of 0.<\/li>\n\n\n\n
  4. Check if the substring starting from the start index and of length (end-start+1) lies between the hash map or not. If it lies in the hash map check for the next substring.<\/li>\n\n\n\n
  5. If it does not lie between the hashmap call the function by increasing the end to end+1.<\/li>\n\n\n\n
  6. If we reach the last index, return false.<\/li>\n<\/ol>\n\n\n\n

    The time complexity for the above approach is O(n*n) where n is the size of the string. As we are recursively calling the function for all the substrings in contains in a given string. The space complexity of the above code is O(n*n) as we are memorizing our previously calculated values into a 2-D array.<\/p>\n\n\n\n

    But there is a better way possible!<\/p>\n\n\n\n

    Optimized Approach<\/strong><\/h2>\n\n\n\n

    In the above approach, we are storing the values of the array in the hash map which increases our memory. Also, we are storing the starting and ending index of the substring which is laid to space complexity of O(n^2). <\/p>\n\n\n\n

    In the dynamic programming approach to solve the Word Break problem, we will iterate all the words in the array. Check if any of the words can be formed from the substring starting from the start index given to you. If it can be formed check for the index start\u00a0 = start + word. size(). If all the substring contains in the array return true, Otherwise return false.<\/strong><\/p>\n\n\n\n

    Let\u2019s examine the step-by-step approach for the above process.<\/p>\n\n\n\n

      \n
    1. First, create an array for memorizing the values of the string. Initialize all the values with -1.<\/li>\n\n\n\n
    2. Create a function that will check if we can break the string or not. The function took parameters starting index, string, array, and the memorized array.<\/li>\n\n\n\n
    3. Check if the starting index is equal to the size of the string if it returns 0. As we are out of the string.<\/li>\n\n\n\n
    4. If not, check if we had previously checked for this index or not. If dp[ start ] == -1 means we have not checked it yet. If dp[ start ] == 0 means we cannot break that string. If dp[ start] == 1 means we can break the string.<\/li>\n\n\n\n
    5. If we had not checked this index, iterated over the array and checked if the substring starting from the start till the word length is the same as the word or not. If it is the same check for index start = start + word. size()<\/strong>. If it is not, return false.<\/li>\n<\/ol>\n\n\n\n

      Let’s now implement it in programming.<\/p>\n\n\n\n

      C++ Code<\/strong><\/h3>\n\n\n\n

      Below is the C++ program for the Word Break problem:<\/p>\n\n\n\n

      #include<bits\/stdc++.h>\nusing namespace std;\n\nbool word_break(int start, string& s, vector<string>& arr, vector<int>& dp){\n\n\u00a0\u00a0\u00a0\u00a0if(dp[start]>=0) return dp[start]? true:false;\n\n\u00a0\u00a0\u00a0\u00a0int n = s.size();\n\n\u00a0\u00a0\u00a0\u00a0bool flag = false;\n\n\u00a0\u00a0\u00a0\u00a0for(int i=0;i<arr.size();i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz = arr[i].size();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(start + sz > n) continue;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0string temp = s.substr(start, sz);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(temp == arr[i]){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(start + sz == n) flag = true;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else flag = flag || word_break(start+sz, s, arr, dp);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if(flag) break;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0if(flag) dp[start] = 1;\n\n\u00a0\u00a0\u00a0\u00a0else dp[start] = 0;\n\n\u00a0\u00a0\u00a0\u00a0return flag;\n\n}\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0string s = "favtutor";\n\n\u00a0\u00a0\u00a0\u00a0vector<string>v = {"tut", "fav", "o", "r", "ot"};\n\n\u00a0\u00a0\u00a0\u00a0\/\/ dp array for memorizing.\n\u00a0\u00a0\u00a0\u00a0vector<int>dp(s.size()+2,-1);\n\n\u00a0\u00a0\u00a0\u00a0(word_break(0, s, v, dp))? cout<<"True"<<endl: cout<<"False"<<endl;\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n
      Java Code<\/strong><\/h3>\n\n\n\n
      You can do it with Java also:<\/p>\n\n\n\n
      import java.util.*;\n\npublic class WordBreak {\n\n\u00a0\u00a0\u00a0\u00a0static boolean wordBreak(int start, String s, List<String> arr, int[] dp) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (dp[start] >= 0) return dp[start] == 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int n = s.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0boolean flag = false;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (String word : arr) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int sz = word.length();\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (start + sz > n) continue;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String temp = s.substring(start, start + sz);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (temp.equals(word)) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (start + sz == n) flag = true;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else flag = flag || wordBreak(start + sz, s, arr, dp);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if (flag) break;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0dp[start] = flag ? 1 : 0;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return flag;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0String s = "favtutor";\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0List<String> v = Arrays.asList("tut", "fav", "o", "r", "ot");\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ dp array for memorizing.\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int[] dp = new int[s.length() + 2];\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Arrays.fill(dp, -1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println(wordBreak(0, s, v, dp) ? "True" : "False");\n\u00a0\u00a0\u00a0\u00a0}\n}<\/pre><\/div>\n\n\n\n
      Python Code<\/strong><\/h3>\n\n\n\n
      Here is the proper Python implementation:<\/p>\n\n\n\n
      def word_break(start, s, arr, dp):\n\n\u00a0\u00a0\u00a0\u00a0if dp[start] >= 0:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return dp[start] == 1\n\n\u00a0\u00a0\u00a0\u00a0n = len(s)\n\n\u00a0\u00a0\u00a0\u00a0flag = False\n\n\u00a0\u00a0\u00a0\u00a0for word in arr:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0sz = len(word)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if start + sz > n:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0continue\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0temp = s[start:start + sz]\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if temp == word:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if start + sz == n:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0flag = True\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0else:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0flag = flag or word_break(start + sz, s, arr, dp)\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0if flag:\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0break\n\n\u00a0\u00a0\u00a0\u00a0dp[start] = 1 if flag else 0\n\n\u00a0\u00a0\u00a0\u00a0return flag\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0s = "favtutor"\n\n\u00a0\u00a0\u00a0\u00a0v = ["tut", "fav", "o", "r", "ot"]\n\n\u00a0\u00a0\u00a0\u00a0# dp array for memorizing.\n\n\u00a0\u00a0\u00a0\u00a0dp = [-1] * (len(s) + 2)\n\n\u00a0\u00a0\u00a0\u00a0print("True" if word_break(0, s, v, dp) else "False")<\/pre><\/div>\n\n\n\n
      Output:<\/strong><\/p>\n\n\n\n
      True<\/code><\/pre>\n\n\n\n
      The time complexity for the above code is O(n*m). Where n is the size of the string and m is the size of the array given to you. As we are iterating over each index of the string and while iterating we are checking for each word present in the array. The space complexity is reduced to O(n) as we are not storing the array values in the hash map.<\/p>\n\n\n\n
      Let’s compare both approaches in the end:<\/p>\n\n\n\n
      Approach<\/th>Time Complexity<\/th>Space Complexity<\/th>Description<\/th><\/tr><\/thead>
      Brute Force<\/td>O(n*n)<\/td>O(n*n)<\/td>We are storing the values in the 2D- array which is laid to the space complexity of O(n*n).<\/td><\/tr>
      Optimized     <\/td>O(n*m)<\/td>O(n)<\/td>We are checking at each index if any substring forms a word that lies in the array.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Conclusion<\/strong><\/h2>\n\n\n\n
      In this article, we see various approaches to solving the Word Break leetcode<\/a> problem. It helps us to determine which approach is best by time and space complexity. We can also see how calling the loop inside the function reduced our time complexity. <\/p>\n","protected":false},"excerpt":{"rendered":"
      Get the solution for the famous Word Break problem from leetcode using dynamic programming by implementing it in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":2107,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-2104","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2104","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2104"}],"version-history":[{"count":8,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2104\/revisions"}],"predecessor-version":[{"id":2134,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2104\/revisions\/2134"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2107"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2104"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2104"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2104"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}