Suppose we have one input string, a partitioning of that string is palindrome partitioning, when every substring of the partition is a palindrome. In this section, we have to ﬁnd the minimum cuts are needed to palindrome partitioning the given string. So if the string is like “ababbbabbababa” Minimum cut to partition as palindrome. Here 3 cuts are needed. The palindromes are: a | babbbab | b | ababa To solve this, we will follow these steps − n := length of str deﬁne cut matrix and pal matrix each of order n x n for i := 0 to n, do pal[i, i] := true and cut[i, i] := 0 for len in range 2 to n, do for i in range 0 to n – len, do j := i + len – 1 if len = 2, then if str[i] = str[j], then pal[i, j] := true else when str[i] = str[j] and pal[i+1, j-1] ≠ 0 pal[i, j] := true if pal[i, j] is true, then cut[i, j] := 0 else cut[i, j] := ∞ for k in range i to j-1, do cut[i, j] := minimum of cut[i, j] and (cut[i, k]+ cut[k+1, j+1]+1) return cut[0, n-1] Example Let us see the following implementation to get better understanding − #include #include using namespace std; int min (int a, int b){ return (a < b)? a : b; } int minPalPartion(string str){ int n = str.size(); int cut[n][n]; bool pal[n][n]; //true when palindrome present for i to j th element for (int i=0; i

Palindrome Partitioning in C++

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock