Proficient Level
Implement the palindromePartitionCount method that counts palindrome partitions possible for the text.
The input is a string text.
Your task is to count how many ways the string can be split into non-empty substrings so that every substring is a palindrome.
For example, aab has two valid palindrome partitions: a | a | b and aa | b. Therefore, the answer is 2.
Example 1
Input
text (string) =
aabReturns (int)
2Example 2
Input
text (string) =
aReturns (int)
1Example 3
Input
text (string) =
aaaReturns (int)
4Use backtracking to try every possible cut position.
Starting from the current index, take each possible substring ending at or after that index. If the substring is a palindrome, continue partitioning the remaining part of the string.
When the current index reaches the end of the string, one complete palindrome partition has been formed, so increase the count.
Pseudocode:
function palindromePartitionCount(text):
count = 0
backtrack(start):
if start == length of text:
count++
return
for end from start to length of text - 1:
if isPalindrome(text, start, end):
backtrack(end + 1)
backtrack(0)
return count
function isPalindrome(text, left, right):
while left < right:
if text[left] != text[right]:
return false
left++
right--
return trueReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run