{"id":49,"date":"2017-09-02T16:48:16","date_gmt":"2017-09-02T23:48:16","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=49"},"modified":"2018-08-28T22:42:40","modified_gmt":"2018-08-29T05:42:40","slug":"leetcode-139-word-break","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/leetcode\/leetcode-139-word-break\/","title":{"rendered":"\u82b1\u82b1\u9171 Leetcode 139. Word Break"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 139. Word Break (revisit) - \u5237\u9898\u627e\u5de5\u4f5c EP28\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/ptlwluzeC1I?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<h1>\n<strong>Problem<\/strong><\/h1>\n<p>Given a\u00a0<b>non-empty<\/b>\u00a0string\u00a0<i>s<\/i>\u00a0and a dictionary\u00a0<i>wordDict<\/i>\u00a0containing a list of\u00a0<b>non-empty<\/b>\u00a0words, determine if\u00a0<i>s<\/i>\u00a0can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.<\/p>\n<p>For example, given<br \/>\n<i>s<\/i>\u00a0=\u00a0<code>\"leetcode\"<\/code>,<br \/>\n<i>dict<\/i>\u00a0=\u00a0<code>[\"leet\", \"code\"]<\/code>.<\/p>\n<p>Return true because\u00a0<code>\"leetcode\"<\/code>\u00a0can be segmented as\u00a0<code>\"leet code\"<\/code>.<\/p>\n<p><b><span style=\"color: red;\">UPDATE (2017\/1\/4):<\/span><\/b><br \/>\nThe\u00a0<i>wordDict<\/i>\u00a0parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.<\/p>\n<p><ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\">\u00a0<\/ins><\/p>\n<h1><strong>Idea:<\/strong><\/h1>\n<p>DP<\/p>\n<p>Time complexity O(n^2)<\/p>\n<p>Space complexity O(n^2)<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/139.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-652\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/139.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/139.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/139-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/139-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/09\/139-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<h1><strong>Solutions:<\/strong><\/h1>\n<p>C++<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\nclass Solution {\r\npublic:\r\n    bool wordBreak(string s, vector&lt;string&gt;&amp; wordDict) {\r\n        \/\/ Create a hashset of words for fast query.\r\n        unordered_set&lt;string&gt; dict(wordDict.cbegin(), wordDict.cend());\r\n        \/\/ Query the answer of the original string.\r\n        return wordBreak(s, dict);\r\n    }\r\n    \r\n    bool wordBreak(const string&amp; s, const unordered_set&lt;string&gt;&amp; dict) {\r\n        \/\/ In memory, directly return.\r\n        if(mem_.count(s)) return mem_[s];\r\n        \/\/ Whole string is a word, memorize and return.\r\n        if(dict.count(s)) return mem_[s]=true;\r\n        \/\/ Try every break point.\r\n        for(int j=1;j&lt;s.length();j++) {\r\n            const string left = s.substr(0,j);\r\n            const string right = s.substr(j);\r\n            \/\/ Find the solution for s.\r\n            if(dict.count(right) &amp;&amp; wordBreak(left, dict))\r\n                return mem_[s]=true;\r\n        }\r\n        \/\/ No solution for s, memorize and return.\r\n        return mem_[s]=false;\r\n    }\r\nprivate:\r\n    unordered_map&lt;string, bool&gt; mem_;\r\n};<\/pre>\n<p>C++ V2 without using dict. Updated: 1\/9\/2018<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 9 ms\r\nclass Solution {\r\npublic:\r\n    bool wordBreak(string s, vector&lt;string&gt;&amp; wordDict) {\r\n      \/\/ Mark evert word as breakable.\r\n      for (const string&amp; word : wordDict)\r\n        mem_.emplace(word, true);\r\n\r\n      \/\/ Query the answer of the original string.\r\n      return wordBreak(s);\r\n    }\r\n    \r\n    bool wordBreak(const string&amp; s) {\r\n      \/\/ In memory, directly return.\r\n      if (mem_.count(s)) return mem_[s];\r\n\r\n      \/\/ Try every break point.\r\n      for (int j = 1; j &lt; s.length(); j++) {         \r\n          auto it = mem_.find(s.substr(j));\r\n          \/\/ Find the solution for s.\r\n          if (it != mem_.end() &amp;&amp; it-&gt;second &amp;&amp; wordBreak(s.substr(0, j)))\r\n            return mem_[s] = true;\r\n      }\r\n      \r\n      \/\/ No solution for s, memorize and return.\r\n      return mem_[s] = false;\r\n    }\r\nprivate:\r\n    unordered_map&lt;string, bool&gt; mem_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 13 ms\r\nclass Solution {\r\n    public boolean wordBreak(String s, List&lt;String&gt; wordDict) {\r\n        Set&lt;String&gt; dict = new HashSet&lt;String&gt;(wordDict);\r\n        Map&lt;String, Boolean&gt; mem = new HashMap&lt;String, Boolean&gt;();\r\n        return wordBreak(s, mem, dict);\r\n    }\r\n\r\n    private boolean wordBreak(String s,\r\n                              Map&lt;String, Boolean&gt; mem, \r\n                              Set&lt;String&gt; dict) {\r\n        if (mem.containsKey(s)) return mem.get(s);\r\n        if (dict.contains(s)) {\r\n            mem.put(s, true);\r\n            return true;\r\n        }\r\n        \r\n        for (int i = 1; i &lt; s.length(); ++i) {\r\n            if (dict.contains(s.substring(i)) &amp;&amp; wordBreak(s.substring(0, i), mem, dict)) {\r\n                mem.put(s, true);\r\n                return true;\r\n            }\r\n        }\r\n        \r\n        mem.put(s, false);\r\n        return false;\r\n    }\r\n}<\/pre>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 42 ms\r\n\"\"\"\r\nclass Solution(object):\r\n    def wordBreak(self, s, wordDict):\r\n        def canBreak(s, m, wordDict):\r\n            if s in m: return m[s]\r\n            if s in wordDict: \r\n                m[s] = True\r\n                return True\r\n            \r\n            for i in range(1, len(s)):\r\n                r = s[i:]\r\n                if r in wordDict and canBreak(s[0:i], m, wordDict):\r\n                    m[s] = True\r\n                    return True\r\n            \r\n            m[s] = False\r\n            return False\r\n            \r\n        return canBreak(s, {}, set(wordDict))<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given a\u00a0non-empty\u00a0string\u00a0s\u00a0and a dictionary\u00a0wordDict\u00a0containing a list of\u00a0non-empty\u00a0words, determine if\u00a0s\u00a0can be segmented into a space-separated sequence of one or more dictionary words. You may assume&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,3],"tags":[26,177,17,4],"class_list":["post-49","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","category-leetcode","tag-dynamic-programming","tag-medium","tag-recursion","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/49","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=49"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/49\/revisions"}],"predecessor-version":[{"id":3745,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/49\/revisions\/3745"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=49"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=49"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=49"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}