LeetCode 132. Palindrome Partitioning II [Hard] [C++] 解題筆記

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

Return the minimum cuts needed for a palindrome partitioning of s.

 

Example 1:

Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Example 2:

Input: s = "a"
Output: 0

Example 3:

Input: s = "ab"
Output: 1

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lower-case English letters only.

想法:

      

        這題要我們求將某一字串分割成數個皆是迴文的子字串至少需要幾次分割，將一個字串分為兩個子字串稱為一次分割。這題有兩種做法，第一種是 DFS + memorize，第二種是 DP 的方式，

兩種方式皆能通過但 DFS 方法非常的慢！

首先 DFS 的方法基本上就是利用類似 131. Palindrome Partitioning 的方式將所有解列出來在選出分割次數最少的解作為答案。

第二種方式是 DP 的方式 ( DP 都好難想阿QQ)，首先我們可以先通過一個二維陣列 valid 來紀錄 string 的每個子字串是否是迴文，即 valid[i][j] 表示 s[i~j] 是否為迴文，然後在開始做 DP，利用 dp 矩陣紀錄每個子串要分割成迴文子串的最小次數，即 dp[i] 表示 s[0~i] 的最小分割數，接著我們遍歷 dp[i], i = 0~n -1 ，對於 dp[i] 我們先判斷 s[0~i] 是否本身就是迴文，是的話就不需要分割(分割數為0)，若不是則我們可以將 s[0~i] 拆解為 s[0~j] 與 s[j + 1~i], j < i 來看，即看看從哪一個地方做分割會得到最小分割數，如果 s[j+1~i] 是迴文的話 => 從 j 開始做分割會得到分割數 dp[j] + 1 (1 為分割 s[0~j] 與 s[j+1~i])。

完整程式碼:

解法一 (DFS):

/* DFS with memorize */

class Solution {

public:

int min_cut;

unordered_map<string, int> cuts;

bool isPalindrome(const string& s, int l, int r) {

while (l < r) {

if (s[l++] != s[r--]) { return false; }

}

return true;

}

void dfs(const string& s, const int& start, int& cut, const int& n) {

if (cut >= min_cut) { return; }

auto sub = s.substr(start);

if (isPalindrome(s, start, n - 1)) {

min_cut = min(min_cut, cut);

cuts[sub] = 0;

return;

}

int cur_min = cut;

auto it = cuts.find(sub);

if (it != cuts.end()) {

min_cut = min(min_cut, cut + it->second);

return;

}

for (int i = start; i < n; i++) {

if (isPalindrome(s, start, i)) {

cut++;

dfs(s, i + 1, cut, n);

cut--;

}

}

cuts[sub] = min_cut - cur_min;

return;

}

int minCut(string s) {

min_cut = INT_MAX;

int n = s.size();

if (isPalindrome(s, 0, n - 1)) { return 0; }

int cut = 0;

dfs(s, 0, cut, n);

return min_cut;

}

};

解法二(DP):

/* DP solution, O(n^2) time, O(n^2) space */

class Solution {

public:

int minCut(string s) {

//int n = s.size();

const int n = s.length();

// valid[i][j] means that s[i~j] is palindrome or not

vector<vector<int>> valid(n, vector<int>(n, 1));

// enurmate all length substring to check if it is palindrome or not

for (int l = 2; l <= n; l++) {

for (int i = 0, j = i + l - 1; j < n; i++, j++) {

// 比較兩端點是否一樣, 中間的字串是否為回文已經在前一個長度列舉過因此直接查看 valid[i+1][j-1]

valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1];

}

}

// dp[i] means number of cut for s[0~i]

vector<int> dp(n, n);

for (int i = 0; i < n; i++) {

if (valid[0][i]) {

dp[i] = 0;

continue;

}

for (int j = 0; j < i; j++) {

if (valid[j + 1][i]) {

dp[i] = min(dp[i], dp[j] + 1);

}

}

}

return dp[n - 1];

}

};