According to the problem solution summary of code Capriccio

thinking

This topic involves two key issues:
1. How to cut
2. Judge whether palindrome

In fact, the cutting problem is similar to the combinatorial problem. So we need to use backtracking to cut strings.

For example, for the string abcdef:

Combinatorial problem: after selecting an a, select the second one in bcdef, select b, and then select the third one in cdef.
Cutting problem: after cutting an a, cut the second segment in bcdef, and then cut the third segment in cdef.

Therefore, the cutting problem can also be abstracted into a tree structure, as shown in the figure:

Recursion is used to traverse vertically, for loop is used to traverse horizontally, and the cutting line (that is, the red line in the figure) is cut to the end of the string, indicating that a cutting method has been found.

At this time, it can be found that the backtracking search process of cutting problem is similar to that of combinatorial problem

Cut string

Retrospective Trilogy
Recursive function parameters
The global variable array path stores the substring of the palindrome after cutting, and the two-dimensional array result stores the result set.
startIndex is also required, because the cut places cannot be cut repeatedly, which is consistent with the combination problem.

vector<vector<string>> result;
vector<string> path; // Put the substring of palindromes
void backtracking (const string& s, int startIndex) {

Recursive function termination condition
As can be seen from the above figure, the cutting line startIndex cuts to the end of the string, indicating that a cutting method has been found. At this time, it is the termination condition of recursion in this layer.

void backtracking (const string& s, int startIndex) {
    // If the starting position is greater than or equal to the size of s, a group of segmentation schemes have been found
    if (startIndex >= s.size()) {
        result.push_back(path);
        return;
    }
}

Logic of single layer search
In for (int i = startIndex; I < s.size(); In the I + +) loop, we define the start position startIndex, so [startIndex, i] is the substring to be intercepted.

First, judge whether the substring is a palindrome. If it is a palindrome, add it to the vector path, which is used to record the cut palindrome substring.

for (int i = startIndex; i < s.size(); i++) {
    if (isPalindrome(s, startIndex, i)) { // Is a palindrome substring
        // Get the substring of [startIndex,i] in s
        string str = s.substr(startIndex, i - startIndex + 1);
        path.push_back(str);
    } else {                // If not, skip directly
        continue;
    }
    backtracking(s, i + 1); // Find the substring with i+1 as the starting position
    path.pop_back();        // In the backtracking process, the substring that has been filled in this time will pop up
}

Determine palindrome substring

Determine whether a string is a palindrome.

You can use the double finger needle method. A pointer is from front to back and a pointer is from back to front. If the elements pointed to by the front and back pointers are equal, it is a palindrome string.

 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;
 }

class Solution {
public:
    bool isPalindrome(int start,int end,string &s){
        for(;start<end;start++,end--){
            if(s[start]!=s[end]) return false;
        }
        return true;
    }
    vector<vector<string>>res;
    vector<string> path; // Put the substring of palindromes
    void backtracking(string &s,int startIndex){
        if(startIndex>=s.size()){  // If the starting position is larger than the size of s, it indicates that a group of segmentation schemes have been found
            res.push_back(path);
            return;
        }
        for(int ii=startIndex;ii<s.size();ii++){
            string s1=s.substr(startIndex,ii-startIndex+1);// Get the substring of [startIndex,i] in s

            if(isPalindrome(0,s1.size()-1,s1)==true){// Is a palindrome substring
                path.push_back(s1);
            }else continue;  // Not palindromes, skip
            backtracking(s,ii+1);// Find the substring with i+1 as the starting position

            path.pop_back();
        }
    }
    vector<vector<string>> partition(string s) {
        backtracking(s,0);
        return res;
    }
};

Difficulties in this topic:
Cutting problem can be abstracted as combinatorial problem
How to simulate those cutting lines
How to terminate recursion in cutting problem
How to intercept substring in recursive loop
How to judge palindromes