Print all palindromic partitions of a string
A palindromic partition of a string is a way to break up the string into substrings such that each substring is a palindrome, meaning it reads the same backward as forward. For example, the palindromic partitions of the string "minimum" are.
m i n i m u m m i n i mum m ini m u m m ini mum minim u m
Code Solution
import java.util.ArrayList;
/*
Java program
Print all palindromic partitions of a string
*/
public class Partition
{
// Check that given substring is palindrome or not
public boolean isPalindrome(String text, int first, int last)
{
while (first < last)
{
if (text.charAt(first) != text.charAt(last))
{
// When boundary characters are different
return false;
}
// Change element position
first++;
last--;
}
return true;
}
// Find all palindromic substring in given text
public void palindromicPart(ArrayList < ArrayList < String >> record,
ArrayList < String > track,
int start, int n, String text)
{
if (start >= n)
{
record.add(new ArrayList < String > (track));
}
else
{
for (int i = start; i < n; i++)
{
if (isPalindrome(text, start, i) == true)
{
// Add palindromic substring
track.add(text.substring(start, i + 1));
palindromicPart(record, track, i + 1, n, text);
// Remove added current substring
track.remove(track.size() - 1);
}
}
}
}
public void palindromicSplit(String text)
{
int n = text.length();
ArrayList < ArrayList < String >> record =
new ArrayList < ArrayList < String >> ();
ArrayList < String > track = new ArrayList < String > ();
palindromicPart(record, track, 0, n, text);
// Display calculated palindromic substring
for (int i = 0; i < record.size(); ++i)
{
for (int j = 0; j < record.get(i).size(); ++j)
{
System.out.print(" " + record.get(i).get(j));
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
Partition task = new Partition();
String text = "minimum";
// All palindromic substring
task.palindromicSplit(text);
}
}
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
// Include header file
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
C++ program
Print all palindromic partitions of a string
*/
class Partition
{
public:
// Check that given substring is palindrome or not
bool isPalindrome(string text, int first, int last)
{
while (first < last)
{
if (text[first] != text[last])
{
// When boundary characters are different
return false;
}
// Change element position
first++;
last--;
}
return true;
}
// Find all palindromic substring in given text
void palindromicPart(vector < vector < string > > &record,
vector < string > track,
int start, int n, string text)
{
if (start >= n)
{
record.push_back(track);
}
else
{
for (int i = start; i < n; i++)
{
if (this->isPalindrome(text, start, i) == true)
{
// Add palindromic substring
track.push_back(text.substr(start, i-start+1));
this->palindromicPart(record, track, i + 1, n, text);
// Remove added current substring
track.pop_back();
}
}
}
}
void palindromicSplit(string text)
{
int n = text.length();
vector < vector < string > > record;
vector < string > track;
this->palindromicPart(record, track, 0, n, text);
// Display calculated palindromic substring
for (int i = 0; i < record.size(); ++i)
{
for (int j = 0; j < record.at(i).size(); ++j)
{
cout << " " << record.at(i).at(j);
}
cout << "\n";
}
}
};
int main()
{
Partition *task = new Partition();
string text = "minimum";
// All palindromic substring
task->palindromicSplit(text);
return 0;
}
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program
Print all palindromic partitions of a string
*/
public class Partition
{
// Check that given substring is palindrome or not
public Boolean isPalindrome(String text, int first, int last)
{
while (first < last)
{
if (text[first] != text[last])
{
// When boundary characters are different
return false;
}
// Change element position
first++;
last--;
}
return true;
}
// Find all palindromic substring in given text
public void palindromicPart(List < List < string >> record,
List < string > track, int start,
int n, String text)
{
if (start >= n)
{
record.Add(new List < string > (track));
}
else
{
for (int i = start; i < n; i++)
{
if (this.isPalindrome(text, start, i) == true)
{
// Add palindromic substring
track.Add(text.Substring(start, i + 1 - start));
this.palindromicPart(record, track, i + 1, n, text);
// Remove added current substring
track.RemoveAt(track.Count - 1);
}
}
}
}
public void palindromicSplit(String text)
{
int n = text.Length;
List < List < string >> record = new List < List < string >> ();
List < string > track = new List < string > ();
this.palindromicPart(record, track, 0, n, text);
// Display calculated palindromic substring
for (int i = 0; i < record.Count; ++i)
{
for (int j = 0; j < record[i].Count; ++j)
{
Console.Write(" " + record[i][j]);
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
Partition task = new Partition();
String text = "minimum";
// All palindromic substring
task.palindromicSplit(text);
}
}
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
package main
import "fmt"
/*
Go program
Print all palindromic partitions of a string
*/
// Check that given substring is palindrome or not
func isPalindrome(text string, first int, last int) bool {
for (first < last) {
if text[first] != text[last] {
// When boundary characters are different
return false
}
// Change element position
first++
last--
}
return true
}
// Find all palindromic substring in given text
func palindromicPart(track[]string, start int, n int, text string) {
if start >= n {
fmt.Println(track)
} else {
runes := []rune(text)
for i := start ; i < n ; i++ {
if isPalindrome(text, start, i) == true {
// Add palindromic substring
track = append(track, string(runes[start: i + 1 ]))
palindromicPart(track, i + 1, n, text)
// Remove added current substring
track = track[:len(track)-1]
}
}
}
}
func palindromicSplit(text string) {
var n int = len(text)
var track []string
// Display calculated palindromic substring
palindromicPart(track, 0, n, text)
}
func main() {
var text string = "minimum"
// All palindromic substring
palindromicSplit(text)
}
input
[m i n i m u m]
[m i n i mum]
[m ini m u m]
[m ini mum]
[minim u m]
<?php
/*
Php program
Print all palindromic partitions of a string
*/
class Partition
{
// Check that given substring is palindrome or not
public function isPalindrome($text, $first, $last)
{
while ($first < $last)
{
if ($text[$first] != $text[$last])
{
// When boundary characters are different
return false;
}
// Change element position
$first++;
$last--;
}
return true;
}
// Find all palindromic substring in given text
public function palindromicPart(&$record, $track,
$start, $n, $text)
{
if ($start >= $n)
{
$record[] = $track;
}
else
{
for ($i = $start; $i < $n; $i++)
{
if ($this->isPalindrome($text, $start, $i) == true)
{
// Add palindromic substring
$track[] = substr($text, $start, $i + 1 - $start) ;
$this->palindromicPart($record, $track, $i + 1, $n, $text);
// Remove added current substring
array_pop($track);
}
}
}
}
public function palindromicSplit($text)
{
$n = strlen($text);
$record = array();
$track = array();
$this->palindromicPart($record, $track, 0, $n, $text);
// Display calculated palindromic substring
for ($i = 0; $i < count($record); ++$i)
{
for ($j = 0; $j < count($record[$i]); ++$j)
{
echo(" ".$record[$i][$j]);
}
echo("\n");
}
}
}
function main()
{
$task = new Partition();
$text = "minimum";
// All palindromic substring
$task->palindromicSplit($text);
}
main();
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
/*
Node JS program
Print all palindromic partitions of a string
*/
class Partition
{
// Check that given substring is palindrome or not
isPalindrome(text, first, last)
{
while (first < last)
{
if (text.charAt(first) != text.charAt(last))
{
// When boundary characters are different
return false;
}
// Change element position
first++;
last--;
}
return true;
}
// Find all palindromic substring in given text
palindromicPart(record, track, start, n, text)
{
if (start >= n)
{
record.push([...track]);
}
else
{
for (var i = start; i < n; i++)
{
if (this.isPalindrome(text, start, i) == true)
{
// Add palindromic substring
track.push(text.substring(start, i + 1 ));
this.palindromicPart(record, track, i + 1, n, text);
// Remove added current substring
track.pop();
}
}
}
}
palindromicSplit(text)
{
var n = text.length;
var record = [];
var track = [];
this.palindromicPart(record, track, 0, n, text);
// Display calculated palindromic substring
for (var i = 0; i < record.length; ++i)
{
for (var j = 0; j < record[i].length; ++j)
{
process.stdout.write(" " + record[i][j]);
}
process.stdout.write("\n");
}
}
}
function main()
{
var task = new Partition();
var text = "minimum";
// All palindromic substring
task.palindromicSplit(text);
}
main();
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
# Python 3 program
# Print all palindromic partitions of a string
class Partition :
# Check that given substring is palindrome or not
def isPalindrome(self, text, first, last) :
while (first < last) :
if (text[first] != text[last]) :
# When boundary characters are different
return False
# Change element position
first += 1
last -= 1
return True
# Find all palindromic substring in given text
def palindromicPart(self, record, track, start, n, text) :
if (start >= n) :
record.append(track.copy())
else :
i = start
while (i < n) :
if (self.isPalindrome(text, start, i) == True) :
# Add palindromic substring
track.append(text[start: i + 1])
self.palindromicPart(record, track, i + 1, n, text)
# Remove added current substring
del track[len(track) - 1]
i += 1
def palindromicSplit(self, text) :
n = len(text)
record = []
track = []
self.palindromicPart(record, track, 0, n, text)
i = 0
# Display calculated palindromic substring
while (i < len(record)) :
j = 0
while (j < len(record[i])) :
print(" ", record[i][j], end = "")
j += 1
print(end = "\n")
i += 1
def main() :
task = Partition()
text = "minimum"
# All palindromic substring
task.palindromicSplit(text)
if __name__ == "__main__": main()
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
# Ruby program
# Print all palindromic partitions of a string
class Partition
# Check that given substring is palindrome or not
def isPalindrome(text, first, last)
while (first < last)
if (text[first] != text[last])
# When boundary characters are different
return false
end
# Change element position
first += 1
last -= 1
end
return true
end
# Find all palindromic substring in given text
def palindromicPart(record, track, start, n, text)
if (start >= n)
record.push(track.map(&:clone))
else
i = start
while (i < n)
if (self.isPalindrome(text, start, i) == true)
# Add palindromic substring
track.push(text[start...i + 1])
self.palindromicPart(record, track, i + 1, n, text)
# Remove added current substring
track.delete_at(track.length - 1)
end
i += 1
end
end
end
def palindromicSplit(text)
n = text.length
record = []
track = []
self.palindromicPart(record, track, 0, n, text)
i = 0
# Display calculated palindromic substring
while (i < record.length)
j = 0
while (j < record[i].length)
print(" ", record[i][j])
j += 1
end
print("\n")
i += 1
end
end
end
def main()
task = Partition.new()
text = "minimum"
# All palindromic substring
task.palindromicSplit(text)
end
main()
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
import scala.collection.mutable._;
/*
Scala program
Print all palindromic partitions of a string
*/
class Partition()
{
// Check that given substring is palindrome or not
def isPalindrome(text: String, start: Int, end: Int): Boolean = {
var first = start;
var last = end;
while (first < last)
{
if (text.charAt(first) != text.charAt(last))
{
// When boundary characters are different
return false;
}
// Change element position
first += 1;
last -= 1;
}
return true;
}
// Find all palindromic substring in given text
def palindromicPart(record: ArrayBuffer[ArrayBuffer[String]],
track: ArrayBuffer[String], start: Int,
n: Int, text: String): Unit = {
if (start >= n)
{
record.append(track.clone);
}
else
{
var i: Int = start;
while (i < n)
{
if (isPalindrome(text, start, i) == true)
{
// Add palindromic substring
track += text.substring(start, i + 1);
palindromicPart(record, track, i + 1, n, text);
// Remove added current substring
track.remove(track.size - 1);
}
i += 1;
}
}
}
def palindromicSplit(text: String): Unit = {
var n: Int = text.length();
var record: ArrayBuffer[ArrayBuffer[String]] =
new ArrayBuffer[ArrayBuffer[String]]();
var track: ArrayBuffer[String] =
new ArrayBuffer[String]();
palindromicPart(record, track, 0, n, text);
var i: Int = 0;
// Display calculated palindromic substring
while (i < record.size)
{
var j: Int = 0;
while (j < record(i).size)
{
print(" " + record(i)(j));
j += 1;
}
print("\n");
i += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Partition = new Partition();
var text: String = "minimum";
// All palindromic substring
task.palindromicSplit(text);
}
}
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
import Foundation;
/*
Swift 4 program
Print all palindromic partitions of a string
*/
class Partition
{
// Check that given substring is palindrome or not
func isPalindrome(_ data: String, _ front: Int, _ tail: Int) -> Bool
{
var first = front ;
var last = tail;
let text = Array(data);
while (first < last)
{
if (text[first] != text[last])
{
// When boundary characters are different
return false;
}
// Change element position
first += 1;
last -= 1;
}
return true;
}
// Find all palindromic substring in given text
func palindromicPart(_ record: inout[[String]],
_ track: inout[String], _ start: Int,
_ n: Int, _ text: String)
{
if (start >= n)
{
record.append(track);
}
else
{
var i: Int = start;
while (i < n)
{
if (self.isPalindrome(text, start, i) == true)
{
let s = text.index(text.startIndex, offsetBy: start)
let e = text.index(text.endIndex,
offsetBy: -(n-(1+i)))
// Add palindromic substring
track.append(String(text[s..<e]));
self.palindromicPart(&record, &track, i + 1, n, text);
// Remove added current substring
track.removeLast();
}
i += 1;
}
}
}
func palindromicSplit(_ text: String)
{
let n: Int = text.count;
var record: [[String]] = [[String]]();
var track: [String] = [String]();
self.palindromicPart(&record, &track, 0, n, text);
var i: Int = 0;
// Display calculated palindromic substring
while (i < record.count)
{
var j: Int = 0;
while (j < record[i].count)
{
print(" ", record[i][j], terminator: "");
j += 1;
}
print(terminator: "\n");
i += 1;
}
}
}
func main()
{
let task: Partition = Partition();
let text: String = "minimum";
// All palindromic substring
task.palindromicSplit(text);
}
main();
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
/*
Kotlin program
Print all palindromic partitions of a string
*/
class Partition
{
// Check that given substring is palindrome or not
fun isPalindrome(text: String, start: Int, end: Int): Boolean
{
var first = start;
var last = end;
while (first < last)
{
if (text.get(first) != text.get(last))
{
// When boundary characters are different
return false;
}
// Change element position
first += 1;
last -= 1;
}
return true;
}
// Find all palindromic substring in given text
fun palindromicPart(record: MutableList < MutableList < String >> ,
track : MutableList < String > ,
start : Int, n: Int, text: String): Unit
{
if (start >= n)
{
record.add(track.toMutableList());
}
else
{
var i: Int = start;
while (i < n)
{
if (this.isPalindrome(text, start, i) == true)
{
// Add palindromic substring
track.add(text.substring(start, i + 1));
this.palindromicPart(record, track, i + 1, n, text);
// Remove added current substring
track.removeAt(track.size - 1);
}
i += 1;
}
}
}
fun palindromicSplit(text: String): Unit
{
val n: Int = text.length;
var record: MutableList < MutableList < String >> =
mutableListOf < MutableList < String >> ();
var track =
mutableListOf < String > ();
this.palindromicPart(record, track, 0, n, text);
var i: Int = 0;
// Display calculated palindromic substring
while (i < record.size)
{
var j: Int = 0;
while (j < record[i].size)
{
print(" " + record[i][j]);
j += 1;
}
print("\n");
i += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val task: Partition = Partition();
val text: String = "minimum";
// All palindromic substring
task.palindromicSplit(text);
}
input
m i n i m u m
m i n i mum
m ini m u m
m ini mum
minim u m
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