Given a text and pattern, we need to check if the pattern completely matches the text.
The solution relies on backtracking and recursion.
Time complexity is 2^n ( n is the length of the text). But the space complexity is also mentioned as 2^n.
Since the solution is recursive, where we decide at each step whether to match the characters or not the max depth of the recursive stack should be O(n+p), where p is the length of the pattern.
So how can the space complexity be O(2^n). Can someone please help if my understanding is incorrect.