time: O(N * 2^N): eliminate one additional iteration to check if substring is a palindrome or not
space: O(N * N)
For each character in the string we have 2 choices to create new palindrome substrings, one is to join with previous substring (for(…end++)) and another is to start a new palindrome substring (dfs(..end+1..)). Thus in the worst case there are 2^N palindrome substrings. Each substring will take O(N) time to check if it’s palindrome and O(N) time to generate substring from start to end indexes.
In total we have O(2^N _ (N + N)) = O(2^N _ 2N) = O(N*2^N)
In the second approach we use dp to remove the check for palindrome, but for each palindrome we still need O(N) time to generate substring from start to end indexes. The complexity is still the same O(N*2^N)