What's the Big O runtime of a DFS word search through a matrix?
The complexity will be $O(m*n*4^{s})$ where m is the no. of rows and n is the no. of columns in the 2D matrix and s is the length of the input string. 

When we start searching from a character we have 4 choices of neighbors for the first character and subsequent characters have only 3 or less than 3 choices but we can take it as 4 (permissible slopiness in upper bound). This slopiness would be fine in large matrices. So for each character we have 4 choices. Total no. of characters are $s$ where s is the length of the input string. So one invocation of search function of your implementation would take $O(4^{s})$ time.

Also in worst case the search is invoked for $m*n$ times. So an upper bound would be $O(m∗n∗4^{s})$.