LeetCode: 131. Palindrome Partitioning

I’m come back ! 从今天开始&＃xff0c;争取每天刷一道 LeetCode&＃xff0c;并写一篇相应的题解。

题目描述

Given a string s, partition s such that every substring of the partition is a palindrome.
Return all possible palindrome partitioning of s.

Example:
Input: "aab"
Output:

[["aa","b"],["a","a","b"]
]

解题思路 —— 动态规划构建回文表格&＃xff0c; 深度优先搜索构建 palindrome partitioning

动态规划构建回文表格&＃xff08;bPalindromes&＃xff09;

利用动态规划&＃xff0c; 将给定字符串 s 中的回文子串识别出来&＃xff0c;具体操作如下。
1. 定义。记&＃xff0c; bPalindromes[i][j] 为字符串 s 在区间 [i, j) 的子串为回文串的真值性。如&＃xff0c;s &＃61; aabaa 时&＃xff0c; bPalindromes[1][4] &＃61; true, bPalindromes[1][3] &＃61; false。
2. 初始化。空串 bPalindromes[i][i] 和 单字符串 bPalindromes[i][i&＃43;1] 为回文串。
3. 状态转移方程。s 串在 [i, j) 区间的子串是回文串的充要条件是&＃xff1a;s 串在 [i&＃43;1, j-1) 区间的子串是回文串, 且 s[i] &＃61;&＃61; s[j-1]。即&＃xff1a;bPalindromes[i][j] &＃61; &＃xff08;bPalindromes[i&＃43;1][j-1] && s[i] &＃61;&＃61; s[j-1])。
4. 例子。 当 s &＃61; aabaa 时&＃xff0c;
&＃xff08;0&＃xff09;s 字符串&＃xff1a;

&＃xff08;1&＃xff09;初始化后的回文表格 bPalindromes&＃xff1a;

&＃xff08;2&＃xff09; 状态转移后的回文表格&＃xff1a;

深度优先搜索构建 palindrome partitioning

根据回文表格记录的回文子串信息&＃xff0c;深度优先搜索能拼凑出 s 串的回文子串的所有可能。

AC 代码

class Solution {
private:// 根据待处理字符串 s 构造回文表格&＃xff08;bPalindromes&＃xff09;void ConstructPalindromesTable(vector<vector<bool>>& bPalindromes, const string& s){ // initializing...bPalindromes.resize(s.size()&＃43;1);for(size_t i &＃61; 0; i 1; &＃43;&＃43;i){bPalindromes[i].resize(s.size()&＃43;1, false);}// s 串中的单个字符 [i, i&＃43;1) 一定是回文的// 定义空串 [i, i&＃xff09; 也是回文的for(size_t i &＃61; 0; i 1] &＃61; true;bPalindromes[i][i] &＃61; true;}for(size_t j &＃61; 1; j 1; &＃43;&＃43;j){for(size_t i &＃61; 0; i // [i, j) 是回文串的充要条件: [i&＃43;1, j-1) 是回文串&＃xff0c;且 s[i] &＃61;&＃61; s[j-1]if(bPalindromes[i&＃43;1][j-1] &＃61;&＃61; true && s[i] &＃61;&＃61; s[j-1]){bPalindromes[i][j] &＃61; true;}}}}// 根据回文表格(bPalindromes)构造 “all possible palindrome partitioning of s”void ConstructPalindromes(const vector<vector<bool>>& bPalindromes, const string& s,vector<vector<string>>& palindromes,vector<string>& curPalindrome, int curState){if(curState >&＃61; bPalindromes.size()-1){if(!curPalindrome.empty()) palindromes.push_back(curPalindrome);return;}for(int nextState &＃61; curState&＃43;1; nextState if(bPalindromes[curState][nextState] &＃61;&＃61; true){curPalindrome.push_back(s.substr(curState, nextState-curState));ConstructPalindromes(bPalindromes, s, palindromes, curPalindrome, nextState);curPalindrome.pop_back();}}}
public:vector<vector<string>> partition(string s) {if(s.empty()) return {{}};// bPalindromes[i][j]: s 串的 [i, j) 区间是回文 vector<vector<bool>> bPalindromes; // 构造回文表格ConstructPalindromesTable(bPalindromes, s);// 构造解vector<vector<string>> palindromes;vector<string> curPalindrome;ConstructPalindromes(bPalindromes, s, palindromes, curPalindrome, 0);return palindromes;}
};