LeetCode Hot 100 P131 Palindrome Partitioning

---

Timeline

Timeline

2026-03-16

init

Dynamic programming + backtracking

---

Problem:

P131 Palindrome Partitioning

https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked

Backtracking: find combinations of partition sizes such that each substring is a palindrome

#include <vector>
#include <string>

using std::vector;
using std::string;

class Solution {
    private:
        void __partition(string &s, vector<vector<int> > &sum_vec, vector<int> &curr, int curr_sum)
        {
                int i, n = s.size();

                if (curr_sum == n) {
                        sum_vec.push_back(curr);
                        return;
                }

                for (i = 1; i <= n; i++) {
                        if (curr_sum + i <= n && isPalindrome(s.substr(curr_sum, i))) {
                                curr.push_back(i);
                                __partition(s, sum_vec, curr, curr_sum + i);
                                curr.pop_back();
                        }
                }
        }
        bool isPalindrome(string s)
        {
                int left = 0, right = s.size() - 1;
                while (left < right) {
                        if (s[left] != s[right])
                                return false;
                        left++;
                        right--;
                }
                return true;
        }

    public:
        vector<vector<string> > partition(string s)
        {
                int pos, n = s.size();
                bool flag = false;
                vector<vector<string> > ret;
                vector<vector<int> > sum_vec;
                vector<int> curr;

                __partition(s, sum_vec, curr, 0);

                for (vector<int> &combinatioin : sum_vec) {
                        vector<string> curr_str_vec;
                        pos = 0;

                        for (int size : combinatioin) {
                                curr_str_vec.push_back(s.substr(pos, size));
                                pos += size;
                        }
                        ret.push_back(curr_str_vec);
                }

                return ret;
        }
};

However, the above method of checking palindromes involves a lot of repeated computation, so consider dynamic programming.

We can precompute whether each substring s[i…j] of string s is a palindrome using dynamic programming. Let f(i,j) denote whether s[i…j] is a palindrome, then we have the state transition equation:

$$f(i,j) = True, i≥j$$

$$f(i,j) = f(i+1,j−1) ∧ (s[i]=s[j])$$

After optimization:

#include <vector>
#include <string>

using std::vector;
using std::string;

class Solution {
    private:
        void __partition(string &s, vector<vector<int> > &sum_vec, vector<int> &curr, int curr_sum,
                         vector<vector<bool> > &isPalindrome)
        {
                int i, n = s.size();

                if (curr_sum == n) {
                        sum_vec.push_back(curr);
                        return;
                }

                for (i = 1; i <= n; i++) {
                        if (curr_sum + i <= n && isPalindrome[curr_sum][curr_sum + i - 1]) {
                                curr.push_back(i);
                                __partition(s, sum_vec, curr, curr_sum + i, isPalindrome);
                                curr.pop_back();
                        }
                }
        }

    public:
        vector<vector<string> > partition(string s)
        {
                int pos, n = s.size();
                vector<vector<string> > ret;
                vector<vector<int> > sum_vec;
                vector<int> curr;

                vector<vector<bool> > isPalindrome(n, vector<bool>(n, false));


                for (int i = n - 1; i >= 0; i--) {
                        for (int j = i; j < n; j++) {
                                if (s[i] == s[j]) {
                                        if (j - i <= 2)
                                                isPalindrome[i][j] = true;
                                        else
                                                isPalindrome[i][j] = isPalindrome[i + 1][j - 1];
                                }
                        }
                }

                __partition(s, sum_vec, curr, 0, isPalindrome);

                for (vector<int> &combinatioin : sum_vec) {
                        vector<string> curr_str_vec;
                        pos = 0;

                        for (int size : combinatioin) {
                                curr_str_vec.push_back(s.substr(pos, size));
                                pos += size;
                        }
                        ret.push_back(curr_str_vec);
                }

                return ret;
        }
};

Official solution

class Solution {
private:
    vector<vector<int>> f;
    vector<vector<string>> ret;
    vector<string> ans;
    int n;

public:
    void dfs(const string& s, int i) {
        if (i == n) {
            ret.push_back(ans);
            return;
        }
        for (int j = i; j < n; ++j) {
            if (f[i][j]) {
                ans.push_back(s.substr(i, j - i + 1));
                dfs(s, j + 1);
                ans.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s) {
        n = s.size();
        f.assign(n, vector<int>(n, true));

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];
            }
        }

        dfs(s, 0);
        return ret;
    }
};