Repository: TheAlgorithms/C-Plus-Plus
File: dynamic_programming/palindrome_partitioning.cpp (C++)

Code before:
 * overall time complexity O(n^2)
 * For example: example 1:-
 * String : "nitik"
 * Output : 2 => "n | iti | k"
 * For example: example 2:-
 * String : "ababbbabbababa"
 * Output : 3 => "aba | b | bbabb | ababa"
 * @author [Sujay Kaushik] (https://github.com/sujaykaushik008)
 * @see related problem at [Leetcode] (https://leetcode.com/problems/palindrome-partitioning-ii/)
 */

#include <iostream>   // for io operations
#include <vector>     // for std::vector
#include <algorithm>  // for std::min
#include <cassert>    // for std::assert
#include <climits>    // for INT_MAX

/**
 * @namespace dynamic_programming
 * @brief Dynamic Programming algorithms
 */
namespace dynamic_programming {

    /**
     * @namespace palindrome_partitioning
     * @brief Functions for [Palindrome Partitioning] (https://leetcode.com/problems/palindrome-partitioning-ii/) algorithm
     */
    namespace palindrome_partitioning {

        /**
         * Function implementing palindrome partitioning algorithm using lookup table method.
         * @param str input string
         * @returns minimum number of partitions
         */
        int pal_part(const std::string &str) {

            int n = str.size();

            // creating lookup table for minimum number of cuts
            std::vector<std::vector<int> > cuts(n, std::vector<int>(n, 0));

            // creating lookup table for palindrome checking
            std::vector<std::vector<bool> > is_palindrome(n, std::vector<bool>(n, false));

            // initialization
            for (int i = 0; i < n; i++) {
                is_palindrome[i][i] = true;
                cuts[i][i] = 0;
            }

            for (int len = 2; len <= n; len++) {

Review comment (suggestion):
```suggestion
     * @brief Functions for [Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning-ii/) algorithm
```

Code after:
 * For example: example 1:-
 * String : "nitik"
 * Output : 2 => "n | iti | k"
 * For example: example 2:-
 * String : "ababbbabbababa"
 * Output : 3 => "aba | b | bbabb | ababa"
 * @author [Sujay Kaushik] (https://github.com/sujaykaushik008)
 */

#include <iostream>   // for io operations
#include <vector>     // for std::vector
#include <algorithm>  // for std::min
#include <cassert>    // for std::assert
#include <climits>    // for INT_MAX

/**
 * @namespace dynamic_programming
 * @brief Dynamic Programming algorithms
 */
namespace dynamic_programming {

    /**
     * @namespace palindrome_partitioning
     * @brief Functions for [Palindrome Partitioning](https://leetcode.com/problems/palindrome-partitioning-ii/) algorithm
     */
    namespace palindrome_partitioning {

        /**
         * Function implementing palindrome partitioning algorithm using lookup table method.
         * @param str input string
         * @returns minimum number of partitions
         */
        int pal_part(const std::string &str) {

            int n = str.size();

            // creating lookup table for minimum number of cuts
            std::vector<std::vector<int> > cuts(n, std::vector<int>(n, 0));

            // creating lookup table for palindrome checking
            std::vector<std::vector<bool> > is_palindrome(n, std::vector<bool>(n, false));

            // initialization
            for (int i = 0; i < n; i++) {
                is_palindrome[i][i] = true;
                cuts[i][i] = 0;
            }

            for (int len = 2; len <= n; len++) {
                for (int start_index = 0; start_index < n - len + 1; start_index++) {