kamyu104/LeetCode-Solutions

why is it linear?

AndrewLisuxin opened this issue · 1 comments

AndrewLisuxin commented

LeetCode-Solutions/Python/wildcard-matching.py

Line 18 in 18a7807

elif last_p_ptr != -1:

Seems it is DFS, every time you first match a '*' with empty string. When facing trouble, you trace back to
match it with one char, and so on. Why is it linear?

kamyu104 commented

Yes, you are right. It is not linear.
At worst, it would be Time: O(m * n).