Skip to main content

Palindrome partition using dynamic programming

Here given code implementation process.

/*
    Java Program for
    Palindrome partition using dynamic programming
*/
public class Palindrome
{
	public void palindromicPartition(String text)
	{
		int n = text.length();
		if (n == 0)
		{
			return;
		}
		int k = 0;
		int[][] dp = new int[n + 1][n + 1];
		int[] partition = new int[n];
		// Set initial value of dp
		for (int i = 0; i <= n; ++i)
		{
			for (int j = 0; j <= n; ++j)
			{
				dp[i][j] = 0;
			}
		}
		// Set initial value of partition array
		for (int i = 0; i < n; ++i)
		{
			partition[i] = Integer.MAX_VALUE;
		}
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		for (int i = 0; i < n; ++i)
		{
			dp[i][i] = 1;
		}
		// Calculate palindrome in consecutive substring length of 2
		for (int i = 0; i < n - 1; i++)
		{
			if (text.charAt(i) == text.charAt(i + 1))
			{
				// When consecutive elements is same
				dp[i][i + 1] = 1;
			}
		}
		// Calculate palindrome in length greater than 2
		for (int i = 3; i <= n; ++i)
		{
			for (int j = 0; j < n - i + 1; ++j)
			{
				k = j + i - 1;
				if (text.charAt(j) == text.charAt(k))
				{
					if (dp[j + 1][k - 1] > 0)
					{
						dp[j][k] = 1;
					}
				}
			}
		}
		for (int i = 0; i < n; ++i)
		{
			k = Integer.MAX_VALUE;
			if (dp[0][i] > 0)
			{
				partition[i] = 0;
			}
			else
			{
				for (int j = 0; j < i; j++)
				{
					if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
					{
						// When substring is palindrome
						k = partition[j] + 1;
					}
				}
				partition[i] = k;
			}
		}
		System.out.println(" Given Text : " + text);
		// Display calculated result
		System.out.println(" Partition  : " + partition[n - 1]);
	}
	public static void main(String[] args)
	{
		Palindrome task = new Palindrome();
		// Test A
		//  string = kdkrepaperspop
		//  kdk repaper s pop
		//     -       - -
		//     ➀      ➁ ➂
		//  3 partitions possible by max length
		//  Result = 1
		task.palindromicPartition("kdkrepaperspop");
		// Test B
		//  string = civic
		//  String is already palindrome so no partition
		//  Result = 0
		task.palindromicPartition("civic");
		// Test C
		//  string = abcde
		//  a b c d e
		//   - - - -
		//  Result = 4
		task.palindromicPartition("abcde");
		// Test D
		//  string = axyiniol
		//  a x y ini o l
		//   - - -   - -
		//  Result = 5
		task.palindromicPartition("axyiniol");
	}
}

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
// Include header file
#include <iostream>
#include <string>
#include <limits.h>

using namespace std;
/*
    C++ Program for
    Palindrome partition using dynamic programming
*/
class Palindrome
{
	public: void palindromicPartition(string text)
	{
		int n = text.length();
		if (n == 0)
		{
			return;
		}
		int k = 0;
		int dp[n + 1][n + 1];
		int partition[n];
		// Set initial value of dp
		for (int i = 0; i <= n; ++i)
		{
			for (int j = 0; j <= n; ++j)
			{
				dp[i][j] = 0;
			}
		}
		// Set initial value of partition array
		for (int i = 0; i < n; ++i)
		{
			partition[i] = INT_MAX;
		}
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		for (int i = 0; i < n; ++i)
		{
			dp[i][i] = 1;
		}
		// Calculate palindrome in consecutive substring length of 2
		for (int i = 0; i < n - 1; i++)
		{
			if (text[i] == text[i + 1])
			{
				// When consecutive elements is same
				dp[i][i + 1] = 1;
			}
		}
		// Calculate palindrome in length greater than 2
		for (int i = 3; i <= n; ++i)
		{
			for (int j = 0; j < n - i + 1; ++j)
			{
				k = j + i - 1;
				if (text[j] == text[k])
				{
					if (dp[j + 1][k - 1] > 0)
					{
						dp[j][k] = 1;
					}
				}
			}
		}
		for (int i = 0; i < n; ++i)
		{
			k = INT_MAX;
			if (dp[0][i] > 0)
			{
				partition[i] = 0;
			}
			else
			{
				for (int j = 0; j < i; j++)
				{
					if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
					{
						// When substring is palindrome
						k = partition[j] + 1;
					}
				}
				partition[i] = k;
			}
		}
		cout << " Given Text : " << text << endl;
		// Display calculated result
		cout << " Partition  : " << partition[n - 1] << endl;
	}
};
int main()
{
	Palindrome *task = new Palindrome();
	// Test A
	//  string = kdkrepaperspop
	//  kdk repaper s pop
	//     -       - -
	//     ➀      ➁ ➂
	//  3 partitions possible by max length
	//  Result = 1
	task->palindromicPartition("kdkrepaperspop");
	// Test B
	//  string = civic
	//  String is already palindrome so no partition
	//  Result = 0
	task->palindromicPartition("civic");
	// Test C
	//  string = abcde
	//  a b c d e
	//   - - - -
	//  Result = 4
	task->palindromicPartition("abcde");
	// Test D
	//  string = axyiniol
	//  a x y ini o l
	//   - - -   - -
	//  Result = 5
	task->palindromicPartition("axyiniol");
	return 0;
}

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
// Include namespace system
using System;
/*
    Csharp Program for
    Palindrome partition using dynamic programming
*/
public class Palindrome
{
	public void palindromicPartition(String text)
	{
		int n = text.Length;
		if (n == 0)
		{
			return;
		}
		int k = 0;
		int[,] dp = new int[n + 1,n + 1];
		int[] partition = new int[n];
		// Set initial value of dp
		for (int i = 0; i <= n; ++i)
		{
			for (int j = 0; j <= n; ++j)
			{
				dp[i,j] = 0;
			}
		}
		// Set initial value of partition array
		for (int i = 0; i < n; ++i)
		{
			partition[i] = int.MaxValue;
		}
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		for (int i = 0; i < n; ++i)
		{
			dp[i,i] = 1;
		}
		// Calculate palindrome in consecutive substring length of 2
		for (int i = 0; i < n - 1; i++)
		{
			if (text[i] == text[i + 1])
			{
				// When consecutive elements is same
				dp[i,i + 1] = 1;
			}
		}
		// Calculate palindrome in length greater than 2
		for (int i = 3; i <= n; ++i)
		{
			for (int j = 0; j < n - i + 1; ++j)
			{
				k = j + i - 1;
				if (text[j] == text[k])
				{
					if (dp[j + 1,k - 1] > 0)
					{
						dp[j,k] = 1;
					}
				}
			}
		}
		for (int i = 0; i < n; ++i)
		{
			k = int.MaxValue;
			if (dp[0,i] > 0)
			{
				partition[i] = 0;
			}
			else
			{
				for (int j = 0; j < i; j++)
				{
					if ((dp[j + 1,i] > 0) && k > partition[j] + 1)
					{
						// When substring is palindrome
						k = partition[j] + 1;
					}
				}
				partition[i] = k;
			}
		}
		Console.WriteLine(" Given Text : " + text);
		// Display calculated result
		Console.WriteLine(" Partition  : " + partition[n - 1]);
	}
	public static void Main(String[] args)
	{
		Palindrome task = new Palindrome();
		// Test A
		//  string = kdkrepaperspop
		//  kdk repaper s pop
		//     -       - -
		//     ➀      ➁ ➂
		//  3 partitions possible by max length
		//  Result = 1
		task.palindromicPartition("kdkrepaperspop");
		// Test B
		//  string = civic
		//  String is already palindrome so no partition
		//  Result = 0
		task.palindromicPartition("civic");
		// Test C
		//  string = abcde
		//  a b c d e
		//   - - - -
		//  Result = 4
		task.palindromicPartition("abcde");
		// Test D
		//  string = axyiniol
		//  a x y ini o l
		//   - - -   - -
		//  Result = 5
		task.palindromicPartition("axyiniol");
	}
}

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
package main
import "math"
import "fmt"
/*
    Go Program for
    Palindrome partition using dynamic programming
*/

func palindromicPartition(text string) {
	var n int = len(text)
	if n == 0 {
		return
	}
	var k int = 0
	// Set initial value of dp
	var dp = make([][] int, n + 1)
	for i := 0; i < n + 1; i++ {
		dp[i] = make([] int, n + 1)
	}
	var partition = make([] int, n)
	// Set initial value of partition array
	for i := 0 ; i < n ; i++ {
		partition[i] = math.MaxInt64
	}
	// Set diagonal elements is to 1.
	// 1 indicates palindromic length of each character.
	for i := 0 ; i < n ; i++ {
		dp[i][i] = 1
	}
	// Calculate palindrome in consecutive substring length of 2
	for i := 0 ; i < n - 1 ; i++ {
		if text[i] == text[i + 1] {
			// When consecutive elements is same
			dp[i][i + 1] = 1
		}
	}
	// Calculate palindrome in length greater than 2
	for i := 3 ; i <= n ; i++ {
		for j := 0 ; j < n - i + 1 ; j++ {
			k = j + i - 1
			if text[j] == text[k] {
				if dp[j + 1][k - 1] > 0 {
					dp[j][k] = 1
				}
			}
		}
	}
	for i := 0 ; i < n ; i++ {
		k = math.MaxInt64
		if dp[0][i] > 0 {
			partition[i] = 0
		} else {
			for j := 0 ; j < i ; j++ {
				if (dp[j + 1][i] > 0) && k > partition[j] + 1 {
					// When substring is palindrome
					k = partition[j] + 1
				}
			}
			partition[i] = k
		}
	}
	fmt.Println(" Given Text : ", text)
	// Display calculated result
	fmt.Println(" Partition  : ", partition[n - 1])
}
func main() {

	// Test A
	//  string = kdkrepaperspop
	//  kdk repaper s pop
	//     -       - -
	//     ➀      ➁ ➂
	//  3 partitions possible by max length
	//  Result = 1
	palindromicPartition("kdkrepaperspop")
	// Test B
	//  string = civic
	//  String is already palindrome so no partition
	//  Result = 0
	palindromicPartition("civic")
	// Test C
	//  string = abcde
	//  a b c d e
	//   - - - -
	//  Result = 4
	palindromicPartition("abcde")
	// Test D
	//  string = axyiniol
	//  a x y ini o l
	//   - - -   - -
	//  Result = 5
	palindromicPartition("axyiniol")
}

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
<?php
/*
    Php Program for
    Palindrome partition using dynamic programming
*/
class Palindrome
{
	public	function palindromicPartition($text)
	{
		$n = strlen($text);
		if ($n == 0)
		{
			return;
		}
		$k = 0;
		// Set initial value of dp
		$dp = array_fill(0, $n + 1, array_fill(0, $n + 1, 0));
      	// Set initial value of partition array us PHP_INT_MAX
		$partition = array_fill(0, $n, PHP_INT_MAX);

		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		for ($i = 0; $i < $n; ++$i)
		{
			$dp[$i][$i] = 1;
		}
		// Calculate palindrome in consecutive substring length of 2
		for ($i = 0; $i < $n - 1; $i++)
		{
			if ($text[$i] == $text[$i + 1])
			{
				// When consecutive elements is same
				$dp[$i][$i + 1] = 1;
			}
		}
		// Calculate palindrome in length greater than 2
		for ($i = 3; $i <= $n; ++$i)
		{
			for ($j = 0; $j < $n - $i + 1; ++$j)
			{
				$k = $j + $i - 1;
				if ($text[$j] == $text[$k])
				{
					if ($dp[$j + 1][$k - 1] > 0)
					{
						$dp[$j][$k] = 1;
					}
				}
			}
		}
		for ($i = 0; $i < $n; ++$i)
		{
			$k = PHP_INT_MAX;
			if ($dp[0][$i] > 0)
			{
				$partition[$i] = 0;
			}
			else
			{
				for ($j = 0; $j < $i; $j++)
				{
					if (($dp[$j + 1][$i] > 0) && $k > $partition[$j] + 1)
					{
						// When substring is palindrome
						$k = $partition[$j] + 1;
					}
				}
				$partition[$i] = $k;
			}
		}
		echo(" Given Text : ".$text."\n");
		// Display calculated result
		echo(" Partition  : ".$partition[$n - 1]."\n");
	}
}

function main()
{
	$task = new Palindrome();
	// Test A
	//  string = kdkrepaperspop
	//  kdk repaper s pop
	//     -       - -
	//     ➀      ➁ ➂
	//  3 partitions possible by max length
	//  Result = 1
	$task->palindromicPartition("kdkrepaperspop");
	// Test B
	//  string = civic
	//  String is already palindrome so no partition
	//  Result = 0
	$task->palindromicPartition("civic");
	// Test C
	//  string = abcde
	//  a b c d e
	//   - - - -
	//  Result = 4
	$task->palindromicPartition("abcde");
	// Test D
	//  string = axyiniol
	//  a x y ini o l
	//   - - -   - -
	//  Result = 5
	$task->palindromicPartition("axyiniol");
}
main();

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
/*
    Node JS Program for
    Palindrome partition using dynamic programming
*/
class Palindrome
{
	palindromicPartition(text)
	{
		var n = text.length;
		if (n == 0)
		{
			return;
		}
		var k = 0;
		// Set initial value of dp
		var dp = Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
		var partition = Array(n).fill(Number.MAX_VALUE);
		
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		for (var i = 0; i < n; ++i)
		{
			dp[i][i] = 1;
		}
		// Calculate palindrome in consecutive substring length of 2
		for (var i = 0; i < n - 1; i++)
		{
			if (text.charAt(i) == text.charAt(i + 1))
			{
				// When consecutive elements is same
				dp[i][i + 1] = 1;
			}
		}
		// Calculate palindrome in length greater than 2
		for (var i = 3; i <= n; ++i)
		{
			for (var j = 0; j < n - i + 1; ++j)
			{
				k = j + i - 1;
				if (text.charAt(j) == text.charAt(k))
				{
					if (dp[j + 1][k - 1] > 0)
					{
						dp[j][k] = 1;
					}
				}
			}
		}
		for (var i = 0; i < n; ++i)
		{
			k = Number.MAX_VALUE;
			if (dp[0][i] > 0)
			{
				partition[i] = 0;
			}
			else
			{
				for (var j = 0; j < i; j++)
				{
					if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
					{
						// When substring is palindrome
						k = partition[j] + 1;
					}
				}
				partition[i] = k;
			}
		}
		console.log(" Given Text : " + text);
		// Display calculated result
		console.log(" Partition  : " + partition[n - 1]);
	}
}

function main()
{
	var task = new Palindrome();
	// Test A
	//  string = kdkrepaperspop
	//  kdk repaper s pop
	//     -       - -
	//     ➀      ➁ ➂
	//  3 partitions possible by max length
	//  Result = 1
	task.palindromicPartition("kdkrepaperspop");
	// Test B
	//  string = civic
	//  String is already palindrome so no partition
	//  Result = 0
	task.palindromicPartition("civic");
	// Test C
	//  string = abcde
	//  a b c d e
	//   - - - -
	//  Result = 4
	task.palindromicPartition("abcde");
	// Test D
	//  string = axyiniol
	//  a x y ini o l
	//   - - -   - -
	//  Result = 5
	task.palindromicPartition("axyiniol");
}
main();

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
import sys
#    Python 3 Program for
#    Palindrome partition using dynamic programming
class Palindrome :
	def palindromicPartition(self, text) :
		n = len(text)
		if (n == 0) :
			return
		
		k = 0
		#  Set initial value of dp
		dp = [[0] * (n + 1) for _ in range(n + 1) ]
		partition = [sys.maxsize] * (n)
		
		i = 0
		#  Set diagonal elements is to 1.
		#  1 indicates palindromic length of each character.
		while (i < n) :
			dp[i][i] = 1
			i += 1
		
		i = 0
		#  Calculate palindrome in consecutive substring length of 2
		while (i < n - 1) :
			if (text[i] == text[i + 1]) :
				#  When consecutive elements is same
				dp[i][i + 1] = 1
			
			i += 1
		
		i = 3
		#  Calculate palindrome in length greater than 2
		while (i <= n) :
			j = 0
			while (j < n - i + 1) :
				k = j + i - 1
				if (text[j] == text[k]) :
					if (dp[j + 1][k - 1] > 0) :
						dp[j][k] = 1
					
				
				j += 1
			
			i += 1
		
		i = 0
		while (i < n) :
			k = sys.maxsize
			if (dp[0][i] > 0) :
				partition[i] = 0
			else :
				j = 0
				while (j < i) :
					if ((dp[j + 1][i] > 0) and k > partition[j] + 1) :
						#  When substring is palindrome
						k = partition[j] + 1
					
					j += 1
				
				partition[i] = k
			
			i += 1
		
		print(" Given Text : ", text)
		#  Display calculated result
		print(" Partition  : ", partition[n - 1])
	

def main() :
	task = Palindrome()
	#  Test A
	#   string = kdkrepaperspop
	#   kdk repaper s pop
	#      -       - -
	#      ➀      ➁ ➂
	#   3 partitions possible by max length
	#   Result = 1
	task.palindromicPartition("kdkrepaperspop")
	#  Test B
	#   string = civic
	#   String is already palindrome so no partition
	#   Result = 0
	task.palindromicPartition("civic")
	#  Test C
	#   string = abcde
	#   a b c d e
	#    - - - -
	#   Result = 4
	task.palindromicPartition("abcde")
	#  Test D
	#   string = axyiniol
	#   a x y ini o l
	#    - - -   - -
	#   Result = 5
	task.palindromicPartition("axyiniol")

if __name__ == "__main__": main()

Output

 Given Text :  kdkrepaperspop
 Partition  :  3
 Given Text :  civic
 Partition  :  0
 Given Text :  abcde
 Partition  :  4
 Given Text :  axyiniol
 Partition  :  5
#    Ruby Program for
#    Palindrome partition using dynamic programming
class Palindrome 
	def palindromicPartition(text) 
		n = text.length
		if (n == 0) 
			return
		end

		k = 0
		#  Set initial value of dp
		dp = Array.new(n + 1) {Array.new(n + 1) {0}}
		partition = Array.new(n) {(2 ** (0.size * 8 - 2))}
		

		i = 0
		#  Set diagonal elements is to 1.
		#  1 indicates palindromic length of each character.
		while (i < n) 
			dp[i][i] = 1
			i += 1
		end

		i = 0
		#  Calculate palindrome in consecutive substring length of 2
		while (i < n - 1) 
			if (text[i] == text[i + 1]) 
				#  When consecutive elements is same
				dp[i][i + 1] = 1
			end

			i += 1
		end

		i = 3
		#  Calculate palindrome in length greater than 2
		while (i <= n) 
			j = 0
			while (j < n - i + 1) 
				k = j + i - 1
				if (text[j] == text[k]) 
					if (dp[j + 1][k - 1] > 0) 
						dp[j][k] = 1
					end

				end

				j += 1
			end

			i += 1
		end

		i = 0
		while (i < n) 
			k = (2 ** (0. size * 8 - 2))
			if (dp[0][i] > 0) 
				partition[i] = 0
			else
 
				j = 0
				while (j < i) 
					if ((dp[j + 1][i] > 0) && k > partition[j] + 1) 
						#  When substring is palindrome
						k = partition[j] + 1
					end

					j += 1
				end

				partition[i] = k
			end

			i += 1
		end

		print(" Given Text : ", text, "\n")
		#  Display calculated result
		print(" Partition  : ", partition[n - 1], "\n")
	end

end

def main() 
	task = Palindrome.new()
	#  Test A
	#   string = kdkrepaperspop
	#   kdk repaper s pop
	#      -       - -
	#      ➀      ➁ ➂
	#   3 partitions possible by max length
	#   Result = 1
	task.palindromicPartition("kdkrepaperspop")
	#  Test B
	#   string = civic
	#   String is already palindrome so no partition
	#   Result = 0
	task.palindromicPartition("civic")
	#  Test C
	#   string = abcde
	#   a b c d e
	#    - - - -
	#   Result = 4
	task.palindromicPartition("abcde")
	#  Test D
	#   string = axyiniol
	#   a x y ini o l
	#    - - -   - -
	#   Result = 5
	task.palindromicPartition("axyiniol")
end

main()

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5

import scala.collection.mutable._;
/*
    Scala Program for
    Palindrome partition using dynamic programming
*/
class Palindrome()
{
	def palindromicPartition(text: String): Unit = {
		var n: Int = text.length();
		if (n == 0)
		{
			return;
		}
		var k: Int = 0;
		// Set initial value of dp
		var dp: Array[Array[Int]] = Array.fill[Int](n + 1, n + 1)(0);
		var partition: Array[Int] = Array.fill[Int](n)(Int.MaxValue);
		var i: Int = 0;
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		while (i < n)
		{
			dp(i)(i) = 1;
			i += 1;
		}
		i = 0;
		// Calculate palindrome in consecutive substring length of 2
		while (i < n - 1)
		{
			if (text.charAt(i) == text.charAt(i + 1))
			{
				// When consecutive elements is same
				dp(i)(i + 1) = 1;
			}
			i += 1;
		}
		i = 3;
		// Calculate palindrome in length greater than 2
		while (i <= n)
		{
			var j: Int = 0;
			while (j < n - i + 1)
			{
				k = j + i - 1;
				if (text.charAt(j) == text.charAt(k))
				{
					if (dp(j + 1)(k - 1) > 0)
					{
						dp(j)(k) = 1;
					}
				}
				j += 1;
			}
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			k = Int.MaxValue;
			if (dp(0)(i) > 0)
			{
				partition(i) = 0;
			}
			else
			{
				var j: Int = 0;
				while (j < i)
				{
					if ((dp(j + 1)(i) > 0) && k > partition(j) + 1)
					{
						// When substring is palindrome
						k = partition(j) + 1;
					}
					j += 1;
				}
				partition(i) = k;
			}
			i += 1;
		}
		println(" Given Text : " + text);
		// Display calculated result
		println(" Partition  : " + partition(n - 1));
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Palindrome = new Palindrome();
		// Test A
		//  string = kdkrepaperspop
		//  kdk repaper s pop
		//     -       - -
		//     ➀      ➁ ➂
		//  3 partitions possible by max length
		//  Result = 1
		task.palindromicPartition("kdkrepaperspop");
		// Test B
		//  string = civic
		//  String is already palindrome so no partition
		//  Result = 0
		task.palindromicPartition("civic");
		// Test C
		//  string = abcde
		//  a b c d e
		//   - - - -
		//  Result = 4
		task.palindromicPartition("abcde");
		// Test D
		//  string = axyiniol
		//  a x y ini o l
		//   - - -   - -
		//  Result = 5
		task.palindromicPartition("axyiniol");
	}
}

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
/*
    Swift 4 Program for
    Palindrome partition using dynamic programming
*/
class Palindrome
{
	func palindromicPartition(_ data: String)
	{
      	let text = Array(data);
		let n: Int = text.count;
		if (n == 0)
		{
			return;
		}
		var k: Int = 0;
		// Set initial value of dp
		var dp: [[Int]] = 
          Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1);
		var partition: [Int] = Array(repeating: Int.max, count: n);
		
		var i: Int = 0;
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		while (i < n)
		{
			dp[i][i] = 1;
			i += 1;
		}
		i = 0;
		// Calculate palindrome in consecutive substring length of 2
		while (i < n - 1)
		{
			if (text[i] == text[i + 1])
			{
				// When consecutive elements is same
				dp[i][i + 1] = 1;
			}
			i += 1;
		}
		i = 3;
		// Calculate palindrome in length greater than 2
		while (i <= n)
		{
			var j: Int = 0;
			while (j < n - i + 1)
			{
				k = j + i - 1;
				if (text[j] == text[k])
				{
					if (dp[j + 1][k - 1] > 0)
					{
						dp[j][k] = 1;
					}
				}
				j += 1;
			}
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			k = Int.max;
			if (dp[0][i] > 0)
			{
				partition[i] = 0;
			}
			else
			{
				var j: Int = 0;
				while (j < i)
				{
					if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
					{
						// When substring is palindrome
						k = partition[j] + 1;
					}
					j += 1;
				}
				partition[i] = k;
			}
			i += 1;
		}
		print(" Given Text : ", data);
		// Display calculated result
		print(" Partition  : ", partition[n - 1]);
	}
}
func main()
{
	let task: Palindrome = Palindrome();
	// Test A
	//  string = kdkrepaperspop
	//  kdk repaper s pop
	//     -       - -
	//     ➀      ➁ ➂
	//  3 partitions possible by max length
	//  Result = 1
	task.palindromicPartition("kdkrepaperspop");
	// Test B
	//  string = civic
	//  String is already palindrome so no partition
	//  Result = 0
	task.palindromicPartition("civic");
	// Test C
	//  string = abcde
	//  a b c d e
	//   - - - -
	//  Result = 4
	task.palindromicPartition("abcde");
	// Test D
	//  string = axyiniol
	//  a x y ini o l
	//   - - -   - -
	//  Result = 5
	task.palindromicPartition("axyiniol");
}
main();

Output

 Given Text :  kdkrepaperspop
 Partition  :  3
 Given Text :  civic
 Partition  :  0
 Given Text :  abcde
 Partition  :  4
 Given Text :  axyiniol
 Partition  :  5
/*
    Kotlin Program for
    Palindrome partition using dynamic programming
*/
class Palindrome
{
	fun palindromicPartition(text: String): Unit
	{
		val n: Int = text.length;
		if (n == 0)
		{
			return;
		}
		var k: Int ;
		// Set initial value of dp
		val dp: Array < Array < Int >> = Array(n + 1)
		{
			Array(n + 1)
			{
				0
			}
		};
		val partition: Array < Int > = Array(n)
		{
			Int.MAX_VALUE
		};
		
		var i = 0;
		// Set diagonal elements is to 1.
		// 1 indicates palindromic length of each character.
		while (i < n)
		{
			dp[i][i] = 1;
			i += 1;
		}
		i = 0;
		// Calculate palindrome in consecutive substring length of 2
		while (i < n - 1)
		{
			if (text.get(i) == text.get(i + 1))
			{
				// When consecutive elements is same
				dp[i][i + 1] = 1;
			}
			i += 1;
		}
		i = 3;
		// Calculate palindrome in length greater than 2
		while (i <= n)
		{
			var j: Int = 0;
			while (j < n - i + 1)
			{
				k = j + i - 1;
				if (text.get(j) == text.get(k))
				{
					if (dp[j + 1][k - 1] > 0)
					{
						dp[j][k] = 1;
					}
				}
				j += 1;
			}
			i += 1;
		}
		i = 0;
		while (i < n)
		{
			k = Int.MAX_VALUE;
			if (dp[0][i] > 0)
			{
				partition[i] = 0;
			}
			else
			{
				var j: Int = 0;
				while (j < i)
				{
					if ((dp[j + 1][i] > 0) && k > partition[j] + 1)
					{
						// When substring is palindrome
						k = partition[j] + 1;
					}
					j += 1;
				}
				partition[i] = k;
			}
			i += 1;
		}
		println(" Given Text : " + text);
		// Display calculated result
		println(" Partition  : " + partition[n - 1]);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Palindrome = Palindrome();
	// Test A
	//  string = kdkrepaperspop
	//  kdk repaper s pop
	//     -       - -
	//     ➀      ➁ ➂
	//  3 partitions possible by max length
	//  Result = 1
	task.palindromicPartition("kdkrepaperspop");
	// Test B
	//  string = civic
	//  String is already palindrome so no partition
	//  Result = 0
	task.palindromicPartition("civic");
	// Test C
	//  string = abcde
	//  a b c d e
	//   - - - -
	//  Result = 4
	task.palindromicPartition("abcde");
	// Test D
	//  string = axyiniol
	//  a x y ini o l
	//   - - -   - -
	//  Result = 5
	task.palindromicPartition("axyiniol");
}

Output

 Given Text : kdkrepaperspop
 Partition  : 3
 Given Text : civic
 Partition  : 0
 Given Text : abcde
 Partition  : 4
 Given Text : axyiniol
 Partition  : 5
Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment