{"id":5749,"date":"2019-10-10T08:28:55","date_gmt":"2019-10-10T15:28:55","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5749"},"modified":"2019-10-10T08:29:06","modified_gmt":"2019-10-10T15:29:06","slug":"leetcode-131-palindrome-partitioning","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-131-palindrome-partitioning\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 131. Palindrome Partitioning"},"content":{"rendered":"\n<p>Given a string&nbsp;<em>s<\/em>, partition&nbsp;<em>s<\/em>&nbsp;such that every substring of the partition is a palindrome.<\/p>\n\n\n\n<p>Return all possible palindrome partitioning of&nbsp;<em>s<\/em>.<\/p>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong>&nbsp;\"aab\"\n<strong>Output:<\/strong>\n[\n  [\"aa\",\"b\"],\n  [\"a\",\"a\",\"b\"]\n]<\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: DP<\/strong><\/h2>\n\n\n\n<p>dp[i] := ans of str[0:i]<br>dp[j] = { x + str[i:len] for x in dp[i] }, 0 &lt;= i &lt; len<\/p>\n\n\n\n<p>Time complexity: O(2^n)<br>Space complexity: O(2^n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nbool isPalindrome(const string& s) {\n  const int n = s.length();\n  for (int i = 0; i < n \/ 2; ++i)\n    if (s[i] != s[n - 1 - i]) return false;\n  return true;\n}\n\nclass Solution {\npublic:\n  vector<vector<string>> partition(string s) {    \n    int n = s.length();    \n    vector<vector<vector<string>>> dp(n + 1);    \n    for (int len = 1; len <= n; ++len) {\n      for (int i = 0; i < len; ++i) {\n        string right = s.substr(i, len - i);\n        if (!isPalindrome(right)) continue;\n        if (i == 0) dp[len].push_back({right});\n        for (const auto&#038; p : dp[i]) {\n          dp[len].push_back(p);\n          dp[len].back().push_back(right);\n        }        \n      }\n    }\n    return dp[n];\n  } \n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DFS<\/strong><\/h2>\n\n\n\n<p> Time complexity: O(2^n)<br>Space complexity: O(n) <\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nbool isPalindrome(const string& s, int l, int r) {\n  while (l < r)\n    if (s[l++] != s[r--]) return false;  \n  return true;\n}\n\nclass Solution {\npublic:\n  vector<vector<string>> partition(string s) {    \n    int n = s.length();    \n    vector<vector<string>> ans;\n    vector<string> cur;\n    function<void(int)> dfs = [&](int start) {\n      if (start == n) {\n        ans.push_back(cur);\n        return;\n      }\n      \n      for (int i = start; i < n; ++i) {\n        if (!isPalindrome(s, start, i)) continue;\n        cur.push_back(s.substr(start, i - start + 1));\n        dfs(i + 1);\n        cur.pop_back();\n      }\n    };\n    dfs(0);\n    return ans;\n  } \n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a string&nbsp;s, partition&nbsp;s&nbsp;such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of&nbsp;s. Example: Input:&nbsp;&#8220;aab&#8221; Output: [ [&#8220;aa&#8221;,&#8221;b&#8221;], [&#8220;a&#8221;,&#8221;a&#8221;,&#8221;b&#8221;]&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[33,18,95,4],"class_list":["post-5749","post","type-post","status-publish","format-standard","hentry","category-searching","tag-dfs","tag-dp","tag-palindrome","tag-string","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5749","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=5749"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5749\/revisions"}],"predecessor-version":[{"id":5751,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5749\/revisions\/5751"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5749"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5749"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5749"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}