leetcode:Palindrome Partitioning (字符串瓜分成回文串的所有方式) 【面试算法题】

leetcode:Palindrome Partitioning (字符串分割成回文串的所有方式) 【面试算法题】

 题目：

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

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

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

先做一个动态规划，保存i到j的字串是否是回文串，减小之后的重复计算。

然后dfs去搜索满足条件的分割方式，sign记录当前元素之后是否进行了分割。

index记录dfs对于字符串的遍历深度，当等于长度的时候就是一种符合条件的情况，根据之前sign的分割，把字串数组存入result，最后输出。

bool dp[2000][2000];bool sign[2000];vector<vector<string>> result;class Solution {public:    void dfs(string s,int index)    {        int i;        if(index==s.length())        {            vector<string> f;            string temp;            for(i=0;i<s.length();++i)            {                temp+=s[i];                if(sign[i]==1)                {                    f.push_back(temp);                    temp="";                }            }            result.push_back(f);            return ;        }        for(i=index;i<s.length();++i)        {            if(dp[index][i]==1)            {                sign[i]=1;                dfs(s,i+1);                sign[i]=0;            }        }    }    vector<vector<string>> partition(string s) {        int i,j,k,len=s.length();        memset(dp,0,sizeof(dp));        result.clear();        for(i=0;i<len;++i)        {            for(j=i;j<len;++j)            {                for(k=0;k<(j-i+1)/2;++k)                    if(s[i+k]!=s[j-k])break;                if(k==(j-i+1)/2)dp[i][j]=1;                else dp[i][j]=0;            }        }        dfs(s,0);        return result;    }};//  http://blog.csdn.net/havenoidea