LeetCode 131. Palindrome Partitioning [Medium] [C++] 解題筆記

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"]]

 

Constraints:

• 1 <= s.length <= 16
• s contains only lowercase English letters.

想法:

            這題別無選擇阿，就是直接 DFS 把每種分割列舉出來試試看是不是迴文。

另外判斷迴文的寫法還蠻精簡的，可以學起來。

完整程式碼:

/* O(2^n), DFS solution */

class Solution {

public:

vector<vector<string>> res;

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, vector<string>& cur, const int& n) {

if (start == n) {

res.push_back(cur);

return;

}

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

if (!isPalindrome(s, start, i)) { continue; }

cur.push_back(s.substr(start, i - start + 1));

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

cur.pop_back();

}

}

vector<vector<string>> partition(string s) {

vector<string> cur;

int n = s.size();

dfs(s, 0, cur, n);

return res;

}

};