[LeetCode]131.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”]
]

思路

此题可以用回溯法解决。把字符串s分为前后两个字串 str1, str2；如果str1是回文，加入partition，然后递归str2.

代码

    /**------------------------------------
    *   日期：2015-03-02
    *   作者：SJF0115
    *   题目: 131.Palindrome Partitioning
    *   网址：https://oj.leetcode.com/problems/palindrome-partitioning/
    *   结果：AC
    *   来源：LeetCode
    *   博客：
    ---------------------------------------**/
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;

    class Solution {
    public:
        vector<vector<string> > partition(string s) {
            vector<string> path;
            vector<vector<string> > result;
            int size = s.size();
            if(size <= 0){
                return result;
            }//if
            Partition(s,size,0,path,result);
            return result;
        }
    private:
        // s源字符串 size 源字符串长度 start 分割点
        // path中间结果 result 最终结果
        void Partition(string str,int size,int start,vector<string> &path,vector<vector<string> > &result){
            // 终止条件
            if(start == size){
                result.push_back(path);
                return;
            }//if
            string substr;
            // 分割字符串
            for(int i = start;i < size;++i){
                substr = str.substr(start,i-start+1);
                // 判断是否是回文串
                if(IsPalindrome(substr)){
                    path.push_back(substr);
                    Partition(str,size,i+1,path,result);
                    path.pop_back();
                }//if
            }//for
        }
        // 判断字符串是否是回文串
        bool IsPalindrome(string str){
            int size = str.size();
            if(size == 0){
                return false;
            }//if
            int left = 0;
            int right = size - 1;
            while(left < right) {
                if(str[left] != str[right]) {
                    return false;
                }//if
                left++;
                right--;
            }//while
            return true;
        }
    };

    int main(){
        Solution s;
        string str("aaba");
        vector<vector<string> > result = s.partition(str);
        // 输出
        for(int i = 0;i < result.size();++i){
            for(int j = 0;j < result[i].size();++j){
                cout<<result[i][j]<<" ";
            }//for
            cout<<endl;
        }//for
        return 0;
    }

运行时间

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>