题解 | #分割回文串#

采用递归求解法，将需要分割的字符串分成“前后”两部分，先对“前半”字符串进行判断，若是回文字符串，则采用递归思想对“后半”字符串进行分割。若“前半”字符串不是回文字符串，则增加其长度，继续判断。直至所有情况均被考虑。

c++代码如下：

class Solution {
public:
    /**
     * 
     * @param s string字符串 
     * @return string字符串vector<vector<>>
     */
       vector<vector<string> > partition(string s) {
        // write code here
        vector<string> strvec;
        vector<vector<string>> strvecs;
        mypartition(s, &strvec, &strvecs);
        return strvecs;
    }

    void mypartition(string s, vector<string> *strvec, vector<vector<string>> *strvecs) {
        int len = s.length();
        vector<string> strvectemp;
        if (len == 0) {
            return;
        }
        string s_head, s_tail;
        strvectemp = *strvec;
        for (int len_first_hwstr = 1; len_first_hwstr <= len; len_first_hwstr++) {
           (*strvec) = strvectemp;
            s_head = s.substr(0, len_first_hwstr);
            s_tail = s.substr(len_first_hwstr);
            if (ishwstr(s_head)) {
                (*strvec).push_back(s_head);
                mypartition(s_tail, strvec, strvecs);
            }
            else {
                (*strvec).clear();
                continue;
            }
            if (!(*strvec).empty())    (*strvecs).push_back(((*strvec)));
            (*strvec).clear();

        }

    }


    bool ishwstr(string str) {
        string strre = myreverse(str);
        if (!str.compare(strre))
            return true;
        else
            return false;
    }

    string myreverse(string str) {
        char temp;
        int len = str.length();
        for (int i = 0; i < len / 2; i++) {
            temp = str[i];
            str[i] = str[len - i - 1];
            str[len - i - 1] = temp;
        }
        return str;
    }
};