No. 131 - Palindrome Partitioning
====


---

## [LeetCode 131 -- Palindrome Partitioning](https://leetcode.com/problems/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`.

A palindrome string is a string that reads the same backward as forward.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

---

### 解法

我們可以透過 DFS 找出組成字串的回文子字串以及 backtracking 找出所有可能的組合來解決這個問題。

由下面完整程式碼中，我們可以看到第 15 行 `dfs` 內的 while loop 就是在 DFS 每一層的搜尋中嘗試以相同子字串開頭 `start` 跟不同子字串結尾 `end` 來找出同一層中的所有可能的回文子字串，也就是 backtracking，我們可以看到第 19 行做完 DFS 後，第 20 行會把當前找到的答案去掉去找另外的答案。

找到 `start` 開頭的回文子字串後，第 19 行就是做 DFS 往下一層找回文子字串，而這邊的下一層的意思也就是 `end + 1` 到字串結尾的剩餘子字串。

class Solution {
public:
  bool isPalindrome(string &str, int start, int end) {
    while (start < end)
      if (str[start++] != str[end--])
        return false;
    return true;
  }
  void dfs(string &str, int start, vector<string> &cur_palindrome_list, vector<vector<string>> &res) {
    if (start >= str.length())
      res.push_back(cur_palindrome_list);
    int end = start;
    // backtracking - 每一次的 iteration 就是再找由 start 為起始點的子字串的
    // 另一種回文子字串
    while (end < str.length()) {
      if (isPalindrome(str, start, end)) {
        cur_palindrome_list.push_back(str.substr(start, end - start + 1));
        // DFS - 找到回文子字串後，往剩餘的子字串找回文子字串
        dfs(str, end + 1, cur_palindrome_list, res);
        cur_palindrome_list.pop_back();
      }
      end++;
    }
  }
  vector<vector<string>> partition(string s) {
    vector<vector<string>> res;
    vector<string> cur_palindrome_list;
    dfs(s, 0, cur_palindrome_list, res);
    return res;
  }
};

我們舉一個簡單的例子: `aabb`

我們首先找到第一個回文子字串 `a` 接著繼續往剩餘的子字串找回文子字串
1. `a` 剩餘字串 `abb`
2. `[a,a]` 剩餘字串 `bb`
3. `[a,a,b]` 剩餘字串 `b`
4. `[a,a,b,b]` 剩餘字串 ` `

到此我們就把整個字串都拆成了回文子字串了，再來我們就倒退回找到 `[a,a]` 的時候看看還有沒有其他可能的回文子字串
1. `[a,a]` 剩餘字串 `bb`
2. `[a,a,bb]` 剩餘字串 ` `

我們找到了 `bb` 也可以是回文子字串，這就是一組新的回文子字串的組合。接著我們就繼續退回第一次找回文時找到 `aa` 回文子字串後再繼續做 DFS 找新的組合
1. `[aa]` 剩餘字串 `bb`
2. `[aa,b]` 剩餘字串 `b`
3. `[aa,b,b]` 剩餘字串 ` `

再一次退回 `aa` 找其他可能的組合
1. `[aa]` 剩餘字串 `bb`
2. `[aa, bb]` 剩餘字串 ` `

### 複雜度分析

對於分析時間複雜度，我們把尋找回文子字串拆分成 node 來看，我們可以看到以字串 `aaa` 為例會像下面這樣，第一層就是再找第一組回文子字串，第二成就是依照前面找到的回文子字串找剩餘的可能的回文子字串，所以總共會有 $2^N$ 個 nodes。而每個 node 我們要去判斷其是否為回文，最多需要 $O(N)$ 的時間複雜度，所以時間複雜度為 $O(N2^N)$。

               aaa
        /       |       \
       a        aa      aaa
     /  \       |
   a,a  a,aa   aa,a
   /
 a,a,a  

空間複雜度上，因為要做 DFS 需要 recursive，所以需要存 `dfs` 的 stack，複雜度為 $O(N)$。