一、題目

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”]]
Example 2:

Input: s = “a”
Output: [[“a”]]

Constraints:

1 <= s.length <= 16
s contains only lowercase English letters.

二、題解

class Solution {
public:vector<vector<string>> res;vector<string> path;bool isPalindrome(string s,int start,int end){int i = start,j = end;while(i < j){if(s[i] != s[j]) return false;i++;j--;}return true;}void backtracking(string s,int startIndex){if(startIndex == s.size()){res.push_back(path);return;}for(int i = startIndex;i < s.size();i++){if(isPalindrome(s,startIndex,i)){string tmp = s.substr(startIndex,i - startIndex + 1);path.push_back(tmp);}else continue;backtracking(s,i+1);path.pop_back();}}vector<vector<string>> partition(string s) {backtracking(s,0);return res;}
};