Search code examples
algorithmpalindrome

about algorithm related to palindrome

Working on a problem below, and with a test case, my question is why a single character 'b' is a palindrome?

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

thanks in advance, Lin

Solution

  • Definition of palindrome from wikipedia:

    A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.

    A single character String is palindrome because it satisfies this condition.

    Min cut means the minimum number of cuts you need to put so that all the substrings are palindrome.

    Here is the simplest example: s="aaaabbbb"

    MinCuts should be 1 : "aaaa", "bbbb"

    But in the given example you can have 3,4,5,6 etc cuts. Example with 3 cuts: "aa", "aa", "bb", "bb"

    Also there will always be a solution with minCuts = stringLength-1 as every single character is a palindrome