131 - Palindrome Partitioning

#medium #hard

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:
Input: s = "aab"
Output: [ ["a","a","b"],["aa","b"] ]

class Solution {
public:
    vector<string> path;
    vector<vector<string>> result;

    bool isPalindrome(const string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }

    void backtracking( string s, int startIndex ) {
        if ( startIndex == s.size() ) {
            result.push_back( path );
            return;
        }

        // 判斷切割的字符串符不符合回文串
        for ( int i = startIndex; i < s.size(); i++ ) {
            if ( isPalindrome( s, startIndex, i ) ) {
                string str = s.substr(startIndex, i - startIndex + 1);
                path.push_back( str );
            }
            else {
                continue; // 不是回文，跳過
            }

            backtracking(s, i + 1); // 尋找i+1為起始位置的子串
            path.pop_back(); // 回溯過程，彈出本次已經填在的子串
        }

    }

    vector<vector<string>> partition(string s) {
        backtracking( s , 0 );
        return result;
    }

};