Split String into Palindromes - Coding in a Smart Way

Split String into Palindromes - Coding in a Smart Way

Discussion This is another dynamic programming problem. Note that greedy algorithm does not work here. For example, s = "aaaaaadda", we can split into "aaaaa" & "adda". If we take the longest palindrome "aaaaaa", it will require 2 cuts. Let's find how we can compute the minimum number of cuts. It is actually very simple. We denote numberOfSplits[i] the minimum number of cuts to split the substring starting at s[i]. We also denote s[i, j] the substring from i to j. We might ignore either i or j to denote the substring ending or starting at j or i respectively. The time complexity of the program is O(N3) where N is the length of string s. public static int split(String s) { //numberOfSplits[i] is the minimum number of splits for substring starting at s[i] int [] numberOfSplits = new int[s.length()]; numberOfSplits[s.length() - 1] = 0; for (int i = s.length() - 2; i >= 0; i--) { int minSplit = Integer.MAX_VALUE; for (int j = i; j < s.length(); j++) { if (Palindrome.isPalindrome(s.

Read full article from Split String into Palindromes - Coding in a Smart Way