construct a 2-D array,Arr[strlen][strlen] according to the following rules.
Arr[i][j] = 1 if i = j (they represent string of single char which is Arr[i], a palindrome by definition) Arr[i][j] = Invalid if i > j (only half the table across the leading diagonal would be filled including the diagonal) Now if i < j Arr[i][j] = Arr[i][j-1] + 1 ( if Substring Arr[i....j] is a palindrome) Arr[i][j] = Arr[i][j-1] ( if Substring Arr[i....j] is not a palindrome) Now the Last Column of your table contains the number of palindromes within a string that starts at index i until the end of the string. Adding all the values from last column will give you the total number of substrings within the string that are palindrome. On Wed, Nov 17, 2010 at 5:49 PM, Arif Ali Saiyed <arif.ali.s...@gmail.com>wrote: > Hi Can you explain following with an example > "esign an > e cient al-gorithm to determine the minimum number of palindromes in > adecomposition for a given string, " > are you asking to find the longest palindrome ? > -Arif > > > On Nov 16, 11:51 pm, lichenga2404 <lichenga2...@gmail.com> wrote: > > A palindrome is a string which is identical to itself in reverse > > order. For example > > \ABAAABA" is a palindrome. Given a string, we'd like to break it up > > into the small- > > est possible number of palindromes. Of course, any one-character > > string is a palindrome > > so we can always break a length n string into n palindromes. Design an > > e cient al- > > gorithm to determine the minimum number of palindromes in a > > decomposition for a > > given string, and analyze the running time. You may assume you are > > given a proce- > > dure Palindrome(S) which runs in time O(jSj) and returns true if and > > only if S is a > > palindrome. > > > > How to solve this problem with the dynamic programming method? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
