No. 131 - Palindrome Partitioning

---

LeetCode 131 – 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(N{2}^N)$。

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

空間複雜度上，因為要做 DFS 需要 recursive，所以需要存 dfs 的 stack，複雜度為

$O(N)$。