【LeetCode】131.Palindrome Partitioning回文划分

本文主要是介绍【LeetCode】131.Palindrome Partitioning回文划分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

            

理解：即将一个字符串划分成回文子串，穷举所有的可能。

分析：

           由我的【LeetCode】 5.Longest Palindromic Substring最长回文子串问题  这篇文章分析可知，判断回文子串的问题可以转换为一个动态规划的问题，这里我使用了动态规划来找到所有的回文子串，将其记录到一个二维数组中，然后将这个数据转化成一个等价图，利用一个动态图搜索算法来找到从起始节点到终止节点的路径，每一个节点便是字符串的一个分割点，由此可以得到问题的解。

代码：

<span style="font-size:12px;">class Solution {
public:vector<vector<string>> partition(string s) {int P[s.length()][s.length()];for(int i=0;i<s.length();i++)for(int j=0;j<s.length();j++)P[i][j]=0;for(int i=0;i<s.length();i++)P[i][i]=1;for(int i=0;i<s.length()-1;i++){if(s[i]==s[i+1])P[i][i+1]=1;}for(int len=3;len<=s.length();len++){for(int i=0;i<s.length()-len+1;i++){int j=i+len-1;if(P[i+1][j-1]==1&&s[i]==s[j])P[i][j]=1;}}vector < vector<string> > table[s.length()+1];vector <string> tempPath;table[0].push_back(tempPath);for(int j=1;j<=s.length();j++){for(int i=0;i<j;i++)//找到前置节点{if(P[i][j-1]==1)//若i为其前置节点{for(int k=0;k<table[i].size();k++){vector<string> temp=table[i][k];temp.push_back(s.substr(i,j-i));table[j].push_back(temp);}}}}return table[s.length()];}
};</span>

这篇关于【LeetCode】131.Palindrome Partitioning回文划分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---