Complexity Notes

Complexities Available

Problem-specific Notes

LC22: Generate Parentheses

LC202: Happy Number

LC79: Word Search

Time: $O(N\cdot 3^L)$ where $N$ is number of cells in board and $L$ is length of the word.

LC explanation:

See In worst case we have to travel till last cell of the matrix and now in last cell our recursion depth will go as far $3^L$ , now why not $4^L$ because we never visit the path where we came from, which is the base case. i.e say we found the first letter, and then the second letter. Now, when we traverse, we have 4 possible paths (assume good case), but we will not go back to the first letter again (i.e travel backwards).

Space: $O(L)$ where $L$ is length of the word since this is how the stack would grow.