首页 > 代码库 > 【LeetCode】Palindrome Partitioning

【LeetCode】Palindrome Partitioning

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

空间换时间。

存放每个子串是否为回文串(O(n2))

然后递归来做。可以看做深度优先搜索。

class Solution {public:    bool isPal(string substr)    {        for(string::size_type i = 0, j = substr.size()-1; i < j; i++, j--)        {            if(substr[i] != substr[j])                return false;        }        return true;    }        vector<vector<string>> partition(string s)     {        map<string, bool> m;        //space for time        for(string::size_type i = 0; i < s.size(); i ++)        {            for(string::size_type j = i; j < s.size(); j ++)            {                string sub = s.substr(i, j-i+1);                if(isPal(sub))                    m[sub] = true;                else                    m[sub] = false;            }        }                vector<string> v;        vector<vector<string> > ret;        Helper(s, v, ret, m);        return ret;    }        void Helper(string sub, vector<string> v, vector<vector<string>>& ret, map<string, bool>& m)    {        for(string::size_type st = 0; st < sub.size(); st ++)        {            if(m[sub.substr(0, st+1)])            {                v.push_back(sub.substr(0,st+1));                if(st == sub.size()-1)                    ret.push_back(v);                else                {                    //recursion                    Helper(sub.substr(st+1, sub.size()-1-st), v, ret, m);                    v.pop_back();                }            }        }    }};

 

 判断回文子串的时候可以用DP的思想,若s[i,j]为回文串,并且s[i-1]==s[j+1],则s[i-1,j+1]也为回文串。

class Solution {public:    vector<vector<string>> partition(string s)     {        map<string, bool> m;        //space for time        for(int i = s.size()-1; i >= 0; i --)        {//string::size_type will overflow            for(int j = i; j < s.size(); j ++)            {                m[s.substr(i,j-i+1)] = false;                if(i == j)                    m[s.substr(i,1)] = true;                else                {                    if(s[i] == s[j])                    {                        //s[i,j] or s[i+1, j-1]                        if(j == i+1 || m[s.substr(i+1, j-i-1)])                            m[s.substr(i,j-i+1)] = true;                    }                }            }        }                vector<string> v;        vector<vector<string> > ret;        Helper(s, v, ret, m);        return ret;    }        void Helper(string sub, vector<string> v, vector<vector<string>>& ret, map<string, bool>& m)    {        if(m[sub])        {            v.push_back(sub);            ret.push_back(v);            v.pop_back();        }        //not else        for(string::size_type st = 0; st < sub.size()-1; st ++)        {            if(m[sub.substr(0, st+1)])            {                v.push_back(sub.substr(0,st+1));                //recursion                Helper(sub.substr(st+1, sub.size()-1-st), v, ret, m);                v.pop_back();            }        }    }};

【LeetCode】Palindrome Partitioning