What's the Big O runtime of a DFS word search through a matrix?

The problem is to try and find a word in a 2D matrix of characters:

Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
Example:

board =

['A','B','C','E'],

['S','F','C','S'],

['A','D','E','E']

Given word = "ABCCED", return true.

Given word = "ABCB", return false

Source: https://leetcode.com/problems/word-search/description/*

Solution:

static boolean[][] visited;
    public boolean exist(char[][] board, String word) {
        visited = new boolean[board.length][board[0].length];

        for(int i = 0; i = board.length || i = board[i].length || j < 0 || board[i][j] != word.charAt(index) || visited[i][j]){
            return false;
        }

        visited[i][j] = true;
        if(search(board, word, i-1, j, index+1) || 
           search(board, word, i+1, j, index+1) ||
           search(board, word, i, j-1, index+1) || 
           search(board, word, i, j+1, index+1)){
            return true;
        }

        visited[i][j] = false;
        return false;
    }

Assume we use a DFS to recursively check each character's 4 neighbours. What would be the correct runtime? I've read various thoughts on this but nothing conclusive.

My thoughts:

We have to check every character in the MxN matrix, so that gives us at least M*N.

Then, for each character, we check in four directions for the length of the input string, so that would give us 4*len. But then for each neighbour we go to, we potentially check each of its neighbours too, but only if they haven't already been visited. This is where I get slightly confused and I'm not sure how to calculate the correct runtime for this.

(Edited question to add exact problem and solution)

The complexity will be $O(mn4^{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})$.

StackExchange Computer Science Q#96626, answer score: 16