O (n )решения для решения boggle

Какова наилучшая временная сложность O (n )функции, которая решает проблему, где доска головоломки n на n?

Я чувствую, что это n^2, так как для каждого символа мы должны смотреть на 2(n-1)другие символы. Интервьюер утверждал, что это не n^2для O(1)поиска в словаре -.