} } }

    leetcode—Palindrome 解题呈报

    添加时间:2013-8-2 点击量:

    1.题目描述

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




    也就是给定一个字符串,找出所有可能的划分,每一个划分的每一个字串都是回文串。设这个划分函数为partition_index(string s,int begin,int end)



    2.解题思路




    蛮力法当然是可以解决这个题目,对于一个长度为n的字符串,有2n-1种划分办法,只须要断定每种划分是否满足前提即可,固然不知道暴力法能不克不及在体系里面ac掉,然则如许显然不是一个正常的法度员该干的事。不过蛮力给我们一些启发。我们从为什么蛮力有2n-1种划分办法开端解析。



    当然,这也很轻易解析,对于长度为n的字符串s0s1…sk…sn-1,在sk和sk-1之间我们可以选择截断与不截断,然则,我们可以基于这个思路理出一个递归的思路,那就是,对于字符串sbeginsbegin+1…sbegin+k…sn-1,所有可能满足前提的划分分为两类:



    (1)在sbegin和sbegin+1之间有隔断间隔,这种景象,只需sbegin和partition_index(s,begin+1,n-1)连接起来即可



    (2)在sbegin和sbegin+1之间无隔断间隔,这种景象,需找到至少包含sbegin和sbegin+1的一个回文字符串,若是可以或许找到,比如,sbegin…sbegin+k是一个回文字符串,那么,将这个回文字符串和partition_index(s,k+1,n-1)连接起来,重视,可能找到不止一个包含s0和s1的回文字符串,那么有几许个,就多出几许类划分可能;若是找不到,那么返回空vector.




    3.代码









    #include <iostream>



    #include <vector>



    #include <string>



    #include <iterator>



    using namespace std;



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



    vector<vector<string> > partition_index(string s, int begin, int end);



    bool isPalindrome(string s, int begin,int end);



    int main()



    {



        partition("cdd");



        return 0;



    }



    &#160;



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



    &#160;



        return partition_index(s,0,s.length()-1);



        



    }



    &#160;



    vector<vector<string> > partition_index(string s, int begin, int end)



    {



        vector<vector<string> > result;



    &#160;



        //鸿沟前提



        if(begin == end)



        {



            vector<string> item;



            item.push_back(s.substr(begin,1));       



            result.push_back(item);



            return result;



        }



        if(begin > end) return result;



        



        //若是在begin与begin+1之间有划分



        vector<vector<string> > result_part1;



        result_part1 = partition_index(s,begin+1,end);



        if(!result_part1.empty())



        {



            vector<vector<string> >::iterator iter_vv;



            for(iter_vv = result_part1.begin();iter_vv!=result_part1.end();++iter_vv)



            { 



                vector<string> temp;



                //temp = iter_vv;



                temp.push_back(s.substr(begin,1));



                



                vector<string>::iterator iter_v;



                for(iter_v = (iter_vv).begin();iter_v!= (iter_vv).end();++iter_v)



                {



                    temp.push_back(iter_v);



                }



                result.push_back(temp);



            }



        }



        



        



        //若是在begin和begin+1之间无划分



        int nextSeg = begin +1;



        while(nextSeg<=end)



        {



    &#160;



            //找到了回文字符串



            if(isPalindrome(s,begin,nextSeg))



            {



                vector<vector<string> >result_part2_1;



                result_part2_1  = partition_index(s,nextSeg+1,end);



                if(!result_part2_1.empty())



                {



                    vector<vector<string> >::iterator iter_vv;



                    for(iter_vv = result_part2_1.begin();iter_vv!=result_part2_1.end();++iter_vv)



                    {



                        vector<string> temp;



                  //      temp = iter_vv;



                        temp.push_back(s.substr(begin,nextSeg));



                



                        vector<string>::iterator iter_v;



                        for(iter_v = (iter_vv).begin();iter_v!= (iter_vv).end();++iter_v)



                        {



                            temp.push_back(iter_v);



                        }



                        result.push_back(temp);



                    }



                    



                }



                else



                {



                    vector<string>temp;



                    temp.push_back(s.substr(begin,nextSeg-begin+2));



                    result.push_back(temp);



                }



            }



            //持续找看是否有其他的更长的回文字符串



            nextSeg++;



        }



        



        return result;



            



    }



    &#160;



    &#160;



    //断定字符串由begin 和end 断定的字串是否为回文字符串



    bool isPalindrome(string s, int begin,int end)



    {



        if(begin>end)return false;



        if(begin==end)return true;



        if((begin+1)==end)return s[begin]==s[end];



        else



            if(s[begin]==s[end])



                return isPalindrome(s,begin+1,end-1);



            esle return false;



    }



    &#160;



    真正的心灵世界会告诉你根本看不见的东西,这东西需要你付出思想和灵魂的劳动去获取,然后它会照亮你的生命,永远照亮你的生命。——王安忆《小说家的十三堂课》
    分享到: