O(2^n) as it seems to me, in a really-really worst case:
when at each step you have to explore both trees to full depth (or near full).

A very clever and concise solution, though maybe Java strings will add unneeded worktime too:
substring() is O(length copied), not O(1).

I'd guess it's about O(n^2) for worst case scenario. Slightly better, since it can drop out at success/certain failures even for worst-case, but O(n^2)'s going to be the best estimate. But, for this type of problem, I think that's always going to be the case.

Hum, I'm not really sure, I'm fairly new here. I did mark the issue as resolved on my side, however it is still counted as issue.
Thanks for checking it at your side!

Hi, I think I solved the issue but it still shows up. Should you be closing the issue too?

I've added a few more test cases: in particular tests that deal with border cases.
Marking as resolved, however if you have in mind some specific scenarios that might fail please let me know.
thanks