{"id":26291,"date":"2017-10-26T21:48:07","date_gmt":"2017-10-26T16:18:07","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26291"},"modified":"2017-10-26T21:48:07","modified_gmt":"2017-10-26T16:18:07","slug":"palindrome-partitioning","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/palindrome-partitioning\/","title":{"rendered":"Palindrome Partitioning"},"content":{"rendered":"<p>Given a string, a partitioning of the string is a <em>palindrome partitioning<\/em> if every substring of the partition is a palindrome. <span id=\"more-20293\"><\/span>For example, \u201caba|b|bbabb|a|b|aba\u201d is a palindrome partitioning of \u201cababbbabbababa\u201d. Determine the fewest cuts needed for palindrome partitioning of a given string. For example, minimum 3 cuts are needed for \u201cababbbabbababa\u201d. The three cuts are \u201ca|babbbab|b|ababa\u201d. If a string is palindrome, then minimum 0 cuts are needed. If a string of length n containing all different characters, then minimum n-1 cuts are needed.<\/p>\n<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter size-full wp-image-26388\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Palindrome-Partitioning.png\" alt=\"Palindrome Partitioning\" width=\"770\" height=\"135\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Palindrome-Partitioning.png 770w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Palindrome-Partitioning-300x53.png 300w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Palindrome-Partitioning-768x135.png 768w\" sizes=\"(max-width: 770px) 100vw, 770px\" \/><\/p>\n<p><strong>Solution<\/strong><br \/>\nThis problem is a variation of Matrix Chain Multiplication problem. If the string is palindrome, then we simply return 0. Else, like the Matrix Chain Multiplication problem, we try making cuts at all possible places, recursively calculate the cost for each cut and return the minimum value.<\/p>\n<p>Let the given string be str and minPalPartion() be the function that returns the fewest cuts needed for palindrome partitioning. following is the optimal substructure property.<\/p>\n<pre>\/\/ i is the starting index and j is the ending index. i must be passed as 0 and j as n-1\r\nminPalPartion(str, i, j) = 0 if i == j. \/\/ When string is of length 1.\r\nminPalPartion(str, i, j) = 0 if str[i..j] is palindrome.\r\n\r\n\/\/ If none of the above conditions is true, then minPalPartion(str, i, j) can be \r\n\/\/ calculated recursively using the following formula.\r\nminPalPartion(str, i, j) = Min { minPalPartion(str, i, k) + 1 +\r\n                                 minPalPartion(str, k+1, j) } \r\n                           where k varies from i to j-1<\/pre>\n<p>Following is Dynamic Programming solution. It stores the solutions to subproblems in two arrays P[][] and C[][], and reuses the calculated values.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Dynamic%20Programming%20Solution%20for%20Palindrome%20Partitioning%20Problem%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Climits.h%3E%0A%20%20%0A%2F%2F%20A%20utility%20function%20to%20get%20minimum%20of%20two%20integers%0Aint%20min%20(int%20a%2C%20int%20b)%20%7B%20return%20(a%20%3C%20b)%3F%20a%20%3A%20b%3B%20%7D%0A%20%20%0A%2F%2F%20Returns%20the%20minimum%20number%20of%20cuts%20needed%20to%20partition%20a%20string%0A%2F%2F%20such%20that%20every%20part%20is%20a%20palindrome%0Aint%20minPalPartion(char%20*str)%0A%7B%0A%20%20%20%20%2F%2F%20Get%20the%20length%20of%20the%20string%0A%20%20%20%20int%20n%20%3D%20strlen(str)%3B%0A%20%20%0A%20%20%20%20%2F*%20Create%20two%20arrays%20to%20build%20the%20solution%20in%20bottom%20up%20manner%0A%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%20Minimum%20number%20of%20cuts%20needed%20for%20palindrome%20partitioning%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20of%20substring%20str%5Bi..j%5D%0A%20%20%20%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20true%20if%20substring%20str%5Bi..j%5D%20is%20palindrome%2C%20else%20false%0A%20%20%20%20%20%20%20Note%20that%20C%5Bi%5D%5Bj%5D%20is%200%20if%20P%5Bi%5D%5Bj%5D%20is%20true%20*%2F%0A%20%20%20%20int%20C%5Bn%5D%5Bn%5D%3B%0A%20%20%20%20bool%20P%5Bn%5D%5Bn%5D%3B%0A%20%20%0A%20%20%20%20int%20i%2C%20j%2C%20k%2C%20L%3B%20%2F%2F%20different%20looping%20variables%0A%20%20%0A%20%20%20%20%2F%2F%20Every%20substring%20of%20length%201%20is%20a%20palindrome%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20P%5Bi%5D%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20C%5Bi%5D%5Bi%5D%20%3D%200%3B%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%2F*%20L%20is%20substring%20length.%20Build%20the%20solution%20in%20bottom%20up%20manner%20by%0A%20%20%20%20%20%20%20considering%20all%20substrings%20of%20length%20starting%20from%202%20to%20n.%0A%20%20%20%20%20%20%20The%20loop%20structure%20is%20same%20as%20Matrx%20Chain%20Multiplication%20problem%20(%0A%20%20%20%20%20%20%20See%20http%3A%2F%2Fwww.geeksforgeeks.org%2Farchives%2F15553%20)*%2F%0A%20%20%20%20for%20(L%3D2%3B%20L%3C%3Dn%3B%20L%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20For%20substring%20of%20length%20L%2C%20set%20different%20possible%20starting%20indexes%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3Cn-L%2B1%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20i%2BL-1%3B%20%2F%2F%20Set%20ending%20index%0A%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20L%20is%202%2C%20then%20we%20just%20need%20to%20compare%20two%20characters.%20Else%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20need%20to%20check%20two%20corner%20characters%20and%20value%20of%20P%5Bi%2B1%5D%5Bj-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(L%20%3D%3D%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20(str%5Bi%5D%20%3D%3D%20str%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20(str%5Bi%5D%20%3D%3D%20str%5Bj%5D)%20%26%26%20P%5Bi%2B1%5D%5Bj-1%5D%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20IF%20str%5Bi..j%5D%20is%20palindrome%2C%20then%20C%5Bi%5D%5Bj%5D%20is%200%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(P%5Bi%5D%5Bj%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Make%20a%20cut%20at%20every%20possible%20localtion%20starting%20from%20i%20to%20j%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20and%20get%20the%20minimum%20cost%20cut.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%20INT_MAX%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20for%20(k%3Di%3B%20k%3C%3Dj-1%3B%20k%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%5Bj%5D%20%3D%20min%20(C%5Bi%5D%5Bj%5D%2C%20C%5Bi%5D%5Bk%5D%20%2B%20C%5Bk%2B1%5D%5Bj%5D%2B1)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%2F%2F%20Return%20the%20min%20cut%20value%20for%20complete%20string.%20i.e.%2C%20str%5B0..n-1%5D%0A%20%20%20%20return%20C%5B0%5D%5Bn-1%5D%3B%0A%7D%0A%20%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20char%20str%5B%5D%20%3D%20%22ababbbabbababa%22%3B%0A%20%20%20printf(%22Min%20cuts%20needed%20for%20Palindrome%20Partitioning%20is%20%25d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20minPalPartion(str))%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output :<\/strong><\/p>\n<pre>Min cuts needed for Palindrome Partitioning is 3<\/pre>\n<p>Time Complexity: O(n<sup>3<\/sup>)<\/p>\n[ad type=\u201dbanner\u201d]\n<p><strong>An optimization to above approach<\/strong><br \/>\nIn above approach, we can calculating minimum cut while finding all palindromic substring. If we finding all palindromic substring 1<sup>st<\/sup> and then we calculate minimum cut, time complexity will reduce to O(n<sup>2<\/sup>).<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Dynamic%20Programming%20Solution%20for%20Palindrome%20Partitioning%20Problem%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstring.h%3E%0A%23include%20%3Climits.h%3E%0A%20%20%0A%2F%2F%20A%20utility%20function%20to%20get%20minimum%20of%20two%20integers%0Aint%20min%20(int%20a%2C%20int%20b)%20%7B%20return%20(a%20%3C%20b)%3F%20a%20%3A%20b%3B%20%7D%0A%20%20%0A%2F%2F%20Returns%20the%20minimum%20number%20of%20cuts%20needed%20to%20partition%20a%20string%0A%2F%2F%20such%20that%20every%20part%20is%20a%20palindrome%0Aint%20minPalPartion(char%20*str)%0A%7B%0A%20%20%20%20%2F%2F%20Get%20the%20length%20of%20the%20string%0A%20%20%20%20int%20n%20%3D%20strlen(str)%3B%0A%20%20%0A%20%20%20%20%2F*%20Create%20two%20arrays%20to%20build%20the%20solution%20in%20bottom%20up%20manner%0A%20%20%20%20%20%20%20C%5Bi%5D%20%3D%20Minimum%20number%20of%20cuts%20needed%20for%20palindrome%20partitioning%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20of%20substring%20str%5B0..i%5D%0A%20%20%20%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20true%20if%20substring%20str%5Bi..j%5D%20is%20palindrome%2C%20else%20false%0A%20%20%20%20%20%20%20Note%20that%20C%5Bi%5D%20is%200%20if%20P%5B0%5D%5Bi%5D%20is%20true%20*%2F%0A%20%20%20%20int%20C%5Bn%5D%3B%0A%20%20%20%20bool%20P%5Bn%5D%5Bn%5D%3B%0A%20%20%0A%20%20%20%20int%20i%2C%20j%2C%20k%2C%20L%3B%20%2F%2F%20different%20looping%20variables%0A%20%20%0A%20%20%20%20%2F%2F%20Every%20substring%20of%20length%201%20is%20a%20palindrome%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20P%5Bi%5D%5Bi%5D%20%3D%20true%3B%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%2F*%20L%20is%20substring%20length.%20Build%20the%20solution%20in%20bottom%20up%20manner%20by%0A%20%20%20%20%20%20%20considering%20all%20substrings%20of%20length%20starting%20from%202%20to%20n.%20*%2F%0A%20%20%20%20for%20(L%3D2%3B%20L%3C%3Dn%3B%20L%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20For%20substring%20of%20length%20L%2C%20set%20different%20possible%20starting%20indexes%0A%20%20%20%20%20%20%20%20for%20(i%3D0%3B%20i%3Cn-L%2B1%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20i%2BL-1%3B%20%2F%2F%20Set%20ending%20index%0A%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20L%20is%202%2C%20then%20we%20just%20need%20to%20compare%20two%20characters.%20Else%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20need%20to%20check%20two%20corner%20characters%20and%20value%20of%20P%5Bi%2B1%5D%5Bj-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(L%20%3D%3D%202)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20(str%5Bi%5D%20%3D%3D%20str%5Bj%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20P%5Bi%5D%5Bj%5D%20%3D%20(str%5Bi%5D%20%3D%3D%20str%5Bj%5D)%20%26%26%20P%5Bi%2B1%5D%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(P%5B0%5D%5Bi%5D%20%3D%3D%20true)%0A%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%20%3D%20INT_MAX%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20for(j%3D0%3Bj%3Ci%3Bj%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if(P%5Bj%2B1%5D%5Bi%5D%20%3D%3D%20true%20%26%26%201%2BC%5Bj%5D%3CC%5Bi%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20C%5Bi%5D%3D1%2BC%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20%2F%2F%20Return%20the%20min%20cut%20value%20for%20complete%20string.%20i.e.%2C%20str%5B0..n-1%5D%0A%20%20%20%20return%20C%5Bn-1%5D%3B%0A%7D%0A%20%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20char%20str%5B%5D%20%3D%20%22ababbbabbababa%22%3B%0A%20%20%20printf(%22Min%20cuts%20needed%20for%20Palindrome%20Partitioning%20is%20%25d%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20minPalPartion(str))%3B%0A%20%20%20return%200%3B%0A%7D\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p><strong>Output :<\/strong><\/p>\n<pre>Min cuts needed for Palindrome Partitioning is 3<\/pre>\n<p>Time Complexity: O(n<sup>2<\/sup>)<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>Palindrome Partitioning &#8211; Dynamic Programming a partitioning of the string is a palindrome partitioning if every substring of the partition is a palindrome.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,70145,83623],"tags":[72847,72842,72845,70483,72848,72840,72846,72994,72843,72992,72854,72844,72850,72839,78581,78577,78583,78585,78578,78582,78580,78584,78579,78576,72852,72855,78586,72853,72851],"class_list":["post-26291","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-dynamic-programming","category-palindrome-partitioning","tag-concept-of-dynamic-programming","tag-define-dynamic-programming","tag-definition-of-dynamic-programming","tag-dynamic-programming","tag-dynamic-programming-code-generation-algorithm","tag-dynamic-programming-definition","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-python","tag-dynamic-programming-problems","tag-dynamic-programming-python","tag-dynamic-programming-set-1","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-how-to-solve-dynamic-programming-problems","tag-minimum-cut-palindrome","tag-palindrome-partition-dynamic-programming","tag-palindrome-partitioning-backtracking","tag-palindrome-partitioning-concept","tag-palindrome-partitioning-dynamic-programming","tag-palindrome-partitioning-ii","tag-palindrome-partitioning-in-c-code","tag-palindrome-partitioning-in-dynamic-programming","tag-palindrome-partitioning-java","tag-print-all-palindromic-partitions-of-a-string","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","tag-split-string-into-palindromes","tag-types-of-dynamic-programming","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26291","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26291"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26291\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26291"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26291"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26291"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}