Everything is a palindrome

Computer Science Level 4

Any string can be imagined as a sequence of palindromes because one letter strings are technically palindromes. Let $\text{PalComp}(s)$ be the minimum number of palindromes from which $s$ can be constructed. What is the value of $\text{PalComp}(s)$ of the following

1	`s = "lralhnermakjfipkseokpqlsfjhasgcnpabmpflhiebsnsljjlmlijfnmasoqjeorinsenomsagafjlgklrjnjbmgmpcgkmkrlef"`

Examples

$\text{PalComp}$ ("dadofanna") = $4$ since "dadofanna" $=$ "dad" $+$ "o" $+$ "f" $+$ "anna".

The answer is 87.

2 solutions

Abdelhamid Saadi
Jul 1, 2016

Solution in python:

"Everything is a palindrome"
s = "lralhnermakjfipkseokpqlsfjhasgcnpabmpflhiebsnsljjlmlijfnmasoqjeorinsenomsagafjlgklrjnjbmgmpcgkmkrlef"

def ispalindrome(s):
    return s == s[::-1]

def split(s):
    for k in range(len(s), 0, -1):
        if ispalindrome(s[:k]):
            return (s[:k], s[k:])

def walk(s):
    if len(s) == 0:
        return []
    else:
        ss = split(s)
        return [ss[0]]+ walk(ss[1])

print(len(walk(s)))

Nice solution sir! Thanks!

Harsh Shrivastava - 4 years, 11 months ago

This solution is incorrect. For the string abcbacabcb the code returns $4$ , but the answer should be $2$ , which are a and bcbacabcb .

Christopher Boo - 4 years, 11 months ago

You are right, we need to improve this solution.

Abdelhamid Saadi - 4 years, 10 months ago

Feel free to try a more difficult test case in this problem!

Christopher Boo - 4 years, 10 months ago

Zeeshan Ali
May 12, 2018

def PalComp(s, Dict = {'': 0}):
    '''
    INPUT:
        s: string
        Dict: a dictionary storing values as min number of palindromes constituting corresponding keys
    OUTPUT:
        int: min number of palindromes constituting 's'
    '''
    # Dynamic programing is used with the help of a dict.

    # Base case1 of the recursive relation when PalComp(s) is already known
    if s in Dict:
        return Dict[s]
    # Base case1 of the recursive relation when 's' itself is a Palindrome
    elif isPalindrome(s):
        Dict[s] = 1
        return Dict[s]
    # recursing part of the recursive function
    else:
        # As a worst case scenario, the min number of palindromes that constitute the 's' is equal to the size of 's'
        array = [len(s)]
        # For each possible size of a window traverse the string.
        for i in range(len(s)-1, 0, -1): # length of a window
            # For a certain window of certain size traverse all possible positions
            for start in range(len(s)-i): # shift window
                # if the sub-string in the current window is Palindrome
                if isPalindrome(s[start:start+i]):
                    # count it (as 1)
                    Dict[s[start:start+i]] = 1
                    # recursively call PalComp for the sub-strings to the left and right of the current string
                    Dict[s[:start]] = PalComp(s[:start], Dict)
                    Dict[s[start+i:]] = PalComp(s[start+i:], Dict)
                    # Append this one of the possible results to "array"
                    array.append(1+Dict[s[:start]]+Dict[s[start+i:]])
        # Store the best possible result for 's' to the Dict for future use
        Dict[s] = min(array)
        # Return Dict[s] as the min number of palindromes that constitute the 's'
        return Dict[s]

1	`PalComp("dadofanna")`

4

1	`PalComp("lralhnermakjfipkseokpqlsfjhasgcnpabmpflhiebsnsljjlmlijfnmasoqjeorinsenomsagafjlgklrjnjbmgmpcgkmkrlef")`

87

Everything is a palindrome

The answer is 87.

2 solutions

0 pending reports