Bug Report for https://neetcode.io/problems/search-for-word-ii

Time & Space Complexity for the "Backtracking" solution is incorrect.

It is stated as:

O(m∗n∗4^t+s). Where $m$ is the number of rows, $n$ is the number of columns, $t$ is the maximum length of any word in the array $words$ and $s$ is the sum of the lengths of all the words.

However, this is looser-bound time complexity for the Backtracking (Trie) and Backtracking (Trie + Hash Set)(those bounds are slightly different than O(m∗n∗4^t+s) but are correct).

For "Backtracking", the solution should be:

O(w * m∗n∗4^t).

Reasoning:

In the base backtracking solution, we iterate over every word, and for every word, we try to find a solution. So we need the w component, where w is the number of words we're checking for.

Additionally, we arn't creating a trie in the standalone backtracking solution, so the "+ s" component should not be included.

Finally, we use the tighter bound of 4 * 3^t-1 to be in line with the other solution runtimes. This value comes from the fact that we have 4 options on our first search of the board, but because we don't want to backtrack to the option we just chose, we have 3 remaining options, hence the * 3 component.. the t -1 indicates we've already used one letter from our longest word(t).