# 131. Palindrome Partitioning

### Leetcode

<https://leetcode.com/problems/valid-palindrome/>

### 題目

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.

&#x20;

**Example 1:**

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

**Example 2:**

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

利用 DFS 去 backtracking 所有的迴文子字串

```
var partition = function(s) {
    // 判斷是否迴文
    const isPalindrome = (start, end) => {
        while(start<end) {
            if(s[start++] !== s[end--]) return false;
        }
        return true;
    }
    
    // 回傳結果
    const res = [];
    // 暫存所有為迴文的子字串
    const temp = [];
    
    const dfs = (start) => {
        // 遍歷過一輪後可以把所有迴文子字串加入到結果矩陣
        if(start>=s.length) {
            // 因為後面有 temp.pop()，會將 res 裡的 temp 也清空，所以這裡要複製一份 temp
            res.push([...temp]);
        }
        let end = start;
        // console.log(start, temp)

        while(end < s.length) {
            if(isPalindrome(start, end)) {
                temp.push(s.substring(start, end+1));
                // 在剩餘字串中繼續尋找迴文子字串
                dfs(end+1)
                // 回到上一輪的 temp 矩陣，end++，繼續尋找迴文子字串
                temp.pop();
            }
            end++;
        }
    }
    dfs(0);
    return res;
};
```

Runtime: 244 ms, faster than 87.80% of JavaScript online submissions for Palindrome Partitioning.

Memory Usage: 62.2 MB, less than 74.63% of JavaScript online submissions for Palindrome Partitioning.

**For example:**

s = "aabb"

第一輪從前往後遍歷結束-> temp = \['a', 'a', 'b', 'b']，res  = \[\['a', 'a', 'b', 'b']]

回到上一輪的 temp 矩陣 (temp.pop() 後) -> temp = \['a', 'a', 'b']，start = 3，end = 4

回到上上一輪的 temp 矩陣 (temp.pop() 後) -> temp = \['a', 'a']，start = 2，end = 3

判斷 'bb' 為迴文子字串，將 'bb' 加入 temp -> temp = \['a', 'a', 'bb']，start = 2，end = 3

end+1，繼續 dfs 尋找下一個迴文子字串，如此不斷反覆 backtracking 所有迴文子字串...

* **方法二**

利用 dp 的方式求解，dp\[len] 代表從 0 \~ len 可組成的迴文子字串矩陣

```
var partition = function(s) {
    const isPalindrome = (str) => {
      let start = 0;
      let end = str.length-1;
      while(start<end) {
          if(str[start++] !== str[end--]) return false;
      }
      return true;
    }

    const n = s.length;
    const dp = Array.from(Array(n+1), () => []);
    for(let len=1; len<=n; len++) {
        for(let i=0; i<len; i++) {
            const right = s.substring(i, len);
            if(isPalindrome(right)) {
                // 如果從頭到尾整個字串都是迴文，直接 push 進 dp
                if(i === 0) dp[len].push([right]);
                // 從之前的迴文子字串中尋找，如果 right 是迴文的話
                // 只要把之前迴文子字串的值再加上 right 就是新的迴文子字串了
                for(let arr of dp[i]) {
                    const copyArr = [...arr];
                    copyArr.push(right);
                    dp[len].push(copyArr);
                }
            }
        }
    }
    return dp[n];
};
```

Runtime: 308 ms, faster than 43.76% of JavaScript online submissions for Palindrome Partitioning.

Memory Usage: 71.1 MB, less than 39.12% of JavaScript online submissions for Palindrome Partitioning.

**For example:**

s = "babab"

dp\[0] = \[]

dp\[1] = \[ \[b] ]

dp\[2] = \[ \[b, a] ]

dp\[3] = \[ \[b, a, b], \[bab] ]

dp\[4] = \[ \[b, a, b, a], \[bab, a], \[b, aba] ]

dp\[5] = \[ \[b, a, b, a, b], \[bab, a, b], \[b, aba, b], \[b, a, bab], \[babab] ]

拿 dp\[4] 來觀察，前兩個是由 dp\[3] + 判斷最後一個 a 是迴文計算而來，第三個是根據 dp\[1] + 判斷 aba 迴文而來

### 測資

```
let s = "aab";
// s = "aabb";
// s = "babab";

console.log(partition(s))
```

### 參考資料

<https://hackmd.io/@Ji0m0/B1dUOaRjN/https%3A%2F%2Fhackmd.io%2F%40Ji0m0%2FS1udpfIo_>

<https://zxi.mytechroad.com/blog/searching/leetcode-131-palindrome-partitioning/>
