Problem statement

https://binarysearch.com/problems/Palindrome-Splitting/

Solution

We can use dp here, where dp[i] is number of ways to split s[:i+1].

Complexity

Here complexity is O(n^3), because we do a lot of check for palindromes, it can be made O(n^2) as well.

Code

class Solution:
    def solve(self, s):
        n = len(s)
        @lru_cache(None)
        def dp(i):
            if i == -1: return 1
            return sum(dp(j-1) for j in range(i+1) if s[j:i+1] == s[j:i+1][::-1])

        return dp(n - 1)