Palindrome Partitioning

描述

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",Return

  1.   [
  2.     ["aa","b"],
  3.     ["a","a","b"]
  4.   ]

分析

在每一步都可以判断中间结果是否为合法结果，用回溯法。

一个长度为n的字符串，有n-1个地方可以砍断，每个地方可断可不断，因此复杂度为O(2n−1)O(2^{n-1})

深搜1

  1. // Palindrome Partitioning
  2. // 时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<string>> partition(string s) {
  6.         vector<vector<string>> result;
  7.         vector<string> path;  // 一个partition方案
  8.         dfs(s, path, result, 0, 1);
  9.         return result;
  10.     }
  12.     // prev 表示前一个隔板, start 表示当前隔板
  13.     void dfs(string &s, vector<string>& path,
  14.             vector<vector<string>> &result, size_t prev, size_t start) {
  15.         if (start == s.size()) { // 最后一个隔板
  16.             if (isPalindrome(s, prev, start - 1)) { // 必须使用
  17.                 path.push_back(s.substr(prev, start - prev));
  18.                 result.push_back(path);
  19.                 path.pop_back();
  20.             }
  21.             return;
  22.         }
  23.         // 不断开
  24.         dfs(s, path, result, prev, start + 1);
  25.         // 如果[prev, start-1] 是回文，则可以断开，也可以不断开（上一行已经做了）
  26.         if (isPalindrome(s, prev, start - 1)) {
  27.             // 断开
  28.             path.push_back(s.substr(prev, start - prev));
  29.             dfs(s, path, result, start, start + 1);
  30.             path.pop_back();
  31.         }
  32.     }
  34.     bool isPalindrome(const string &s, int start, int end) {
  35.         while (start < end && s[start] == s[end]) {
  36.             ++start;
  37.             --end;
  38.         }
  39.         return start >= end;
  40.     }
  41. };

深搜2

另一种写法，更加简洁。这种写法也在 Combination Sum, Combination Sum II 中出现过。

  1. // Palindrome Partitioning
  2. // 时间复杂度O(2^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     vector<vector<string>> partition(string s) {
  6.         vector<vector<string>> result;
  7.         vector<string> path;  // 一个partition方案
  8.         DFS(s, path, result, 0);
  9.         return result;
  10.     }
  11.     // 搜索必须以s[start]开头的partition方案
  12.     void DFS(string &s, vector<string>& path,
  13.             vector<vector<string>> &result, int start) {
  14.         if (start == s.size()) {
  15.             result.push_back(path);
  16.             return;
  17.         }
  18.         for (int i = start; i < s.size(); i++) {
  19.             if (isPalindrome(s, start, i)) { // 从i位置砍一刀
  20.                 path.push_back(s.substr(start, i - start + 1));
  21.                 DFS(s, path, result, i + 1);  // 继续往下砍
  22.                 path.pop_back(); // 撤销上上行
  23.             }
  24.         }
  25.     }
  26.     bool isPalindrome(const string &s, int start, int end) {
  27.         while (start < end && s[start] == s[end]) {
  28.             ++start;
  29.             --end;
  30.         }
  31.         return start >= end;
  32.     }
  33. };

动规

  1. // Palindrome Partitioning
  2. // 动规，时间复杂度O(n^2)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     vector<vector<string> > partition(string s) {
  6.         const int n = s.size();
  7.         bool p[n][n]; // whether s[i,j] is palindrome
  8.         fill_n(&p[0][0], n * n, false);
  9.         for (int i = n - 1; i >= 0; --i)
  10.             for (int j = i; j < n; ++j)
  11.                 p[i][j] = s[i] == s[j] && ((j - i < 2) || p[i + 1][j - 1]);
  13.         vector<vector<string> > sub_palins[n]; // sub palindromes of s[0,i]
  14.         for (int i = n - 1; i >= 0; --i) {
  15.             for (int j = i; j < n; ++j)
  16.                 if (p[i][j]) {
  17.                     const string palindrome = s.substr(i, j - i + 1);
  18.                     if (j + 1 < n) {
  19.                         for (auto v : sub_palins[j + 1]) {
  20.                             v.insert(v.begin(), palindrome);
  21.                             sub_palins[i].push_back(v);
  22.                         }
  23.                     } else {
  24.                         sub_palins[i].push_back(vector<string> { palindrome });
  25.                     }
  26.                 }
  27.         }
  28.         return sub_palins[0];
  29.     }
  30. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/dfs/palindrome-partitioning.html