# my c++ 14ms dp and backtracking solution

• The idea of this solution is simple. Record all palindromes of the string s in a 2d array, which will offer a constant look up time later in the recursion.

``````class Solution {
public:
vector<vector<bool>> isPalin(string s) {
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), true));
for(int i = s.size() - 1; i >= 0; i--) {
for(int j = i + 1; j < s.size(); j++) {
if(s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1];
else dp[i][j] = false;
}
}
return dp;
}
void partition(vector<vector<string>>& result, vector<string>& ins, const vector<vector<bool>>& palin, const string& s, int idx) {
if(idx == s.size()) {                   //need to return
result.push_back(ins);
return;
}
for(int i = 1; i <= s.size() - idx; i++) {
if(palin[idx][idx + i - 1]) {
ins.push_back(s.substr(idx, i));
partition(result, ins, palin, s, idx + i);
ins.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
vector<vector<bool>> palin = isPalin(s);
vector<vector<string>> result;
vector<string> ins;
partition(result, ins, palin, s, 0);
return result;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.