palindrome_partitioning.cpp File Reference

Implements Palindrome Partitioning algorithm, giving you the minimum number of partitions you need to make. More...

#include <algorithm>
#include <cassert>
#include <climits>
#include <iostream>
#include <vector>

Include dependency graph for palindrome_partitioning.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	palindrome_partitioning
	Functions for Palindrome Partitioning algorithm.

Functions
int	dynamic_programming::palindrome_partitioning::pal_part (const std::string &str)
static void	test ()
	Test Function.
int	main ()
	Main function.

Detailed Description

Implements Palindrome Partitioning algorithm, giving you the minimum number of partitions you need to make.

palindrome partitioning uses dynamic programming and goes to all the possible partitions to find the minimum you are given a string and you need to give minimum number of partitions needed to divide it into a number of palindromes [Palindrome Partitioning] (https://www.geeksforgeeks.org/palindrome-partitioning-dp-17/) 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)

Definition in file palindrome_partitioning.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 128 of file palindrome_partitioning.cpp.

           {
    test();  // execute the test
    return 0;
}

pal_part()

int dynamic_programming::palindrome_partitioning::pal_part

(

const std::string &

str

)

Function implementing palindrome partitioning algorithm using lookup table method.

Parameters

str	input string

Returns

minimum number of partitions

Definition at line 45 of file palindrome_partitioning.cpp.

                                   {
    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++) {
            int end_index = start_index + len - 1;
 
            if (len == 2) {
                is_palindrome[start_index][end_index] =
                    (str[start_index] == str[end_index]);
            } else {
                is_palindrome[start_index][end_index] =
                    (str[start_index] == str[end_index]) &&
                    is_palindrome[start_index + 1][end_index - 1];
            }
 
            if (is_palindrome[start_index][end_index]) {
                cuts[start_index][end_index] = 0;
            } else {
                cuts[start_index][end_index] = INT_MAX;
                for (int partition = start_index; partition <= end_index - 1;
                     partition++) {
                    cuts[start_index][end_index] =
                        std::min(cuts[start_index][end_index],
                                 cuts[start_index][partition] +
                                     cuts[partition + 1][end_index] + 1);
                }
            }
        }
    }
 
    return cuts[0][n - 1];
}

test()

static void test ( )

static

Test Function.

Returns

void

Definition at line 98 of file palindrome_partitioning.cpp.

                   {
    // custom input vector
    std::vector<std::string> custom_input{"nitik", "ababbbabbababa", "abdc"};
 
    // calculated output vector by pal_part Function
    std::vector<int> calculated_output(3);
 
    for (int i = 0; i < 3; i++) {
        calculated_output[i] =
            dynamic_programming::palindrome_partitioning::pal_part(
                custom_input[i]);
    }
 
    // expected output vector
    std::vector<int> expected_output{2, 3, 3};
 
    // Testing implementation via assert function
    // It will throw error if any of the expected test fails
    // Else it will give nothing
    for (int i = 0; i < 3; i++) {
        assert(expected_output[i] == calculated_output[i]);
    }
 
    std::cout << "All tests passed successfully!\n";
}