My Programming Contest And Problem Solving Profiles

1044 - Palindrome Partitioning

Idea:

i) First, generate all possible palindromic substring (both odd length and even length). And store them in a list.

let str[] = "QWERTYTREWQWERT"

We have a palindrome form  str[0] to str[0]. So we store (0+1) at List[0], which means that if we consider this palindrome we can jump to index [1] to find our next palindrome.  

We have a palindrome form  str[0] to str[10]. So we store (10+1) at List[0], which means that if we consider this palindrome we can jump to 11'th index to find our next palindrome. 

We have a palindrome form  str[4] to str[6]. So we store (6+1) at List[4], which means that if we end our previous palindrome at index [3], then we can consider a palindrome which starts at index[4] and ends at index[6].

2) The second step is to calculate the minimum number of jump needed to reach the end of that string from index[0].

Code