0
$\begingroup$

I am solving an interview practice question:

Partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

My solution is as below, and was accepted.

def partition(self, s: str) -> List[List[str]]:
    
    ans = []
    
    def bt(w, curr):
        if not w:
            ans.append(curr)
        else:
            for l in range(1, len(w)+1):
                chunk = w[:l]
                if ''.join(reversed(chunk)) != chunk:
                    continue
                bt(w[l:], curr + [chunk])
    
    bt(s, [])
    return ans

The time complexity given in the solutions is O(N * 2^N) I do not understand that.

I understand that:

  • there are 2^(N-1) possible partitions,
  • in the worst case any partition yields palindromes,
  • checking for palindrome is linear in the size of the input.

But I am struggling to estimate the amount of work done in the for loop. Why are we multiplying 2^N with just N? What about the linear amount of work done within the body of the loop?

Any insight/hints would be helpful. In conjunction with this, I am unable to write a recurrence relation ..

Thank you very much!!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Lets look at the (worst-case) recurrence for bt:

$$ T(n) = \sum_{l = 1}^{n} (O(l) + T(n-l)) $$

Here $n$ measures the length of the string passed to bt. The sum basically represents the complexity of the loop; for every $l$ you do a $O(l)$ compare operation and in the worst-case call bt with a string of length $n-l$. However we can simplify the above relation in a couple simple steps (using Gauss sum): $$ T(n) = \sum_{l = 1}^{n} (O(l) + T(n-l)) = O(n^2) + \sum_{l = 1}^{n} T(n-l) $$ We can simplify further (we now look at $T(n+1)$): $$ T(n+1) = O((n+1)^2) + \underbrace{\sum_{l = 1}^{n+1} T(n+1-l)}_{\text{index-shift}} \\ = O(n^2+n) + \sum_{l = 0}^{n} T(n-l) \\ = O(n) + T(n) + \underbrace{O(n^2)+ \sum_{l = 1}^{n} T(n-l)}_{ = T(n)} = O(n) + 2T(n) $$ From the recurrence $T(n+1)= cn +2T(n)$ you can maybe already see that we get $O(n2^n)$. Quick proof by induction: Assume $T(n) \leq cn2^n$: $$ T(n+1) = cn + 2T(n) \leq cn + c2n2^n = cn + cn2^{n+1} \\ \leq c2^{n+1}+ cn2^{n+1} = c(n+1)2^{n+1}$$

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.