# 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

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++){
for(int j = 0; j < board[i].length; j++){
if((word.charAt(0) == board[i][j]) && search(board, word, i, j, 0)){
return true;
}
}
}

return false;
}

private boolean search(char[][]board, String word, int i, int j, int index){
if(index == word.length()){
return true;
}

if(i >= board.length || i < 0 || j >= 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)

• Can you edit your question to provide a self-contained description of the problem? I also suggest you show concrete DFS. I'm not sure that DFS is going to suffice to solve the problem you want to solve, so while we could give you the running time for DFS, it might not answer the question you really want answered. – D.W. Aug 26 '18 at 1:44
• Can you spell out your algorithm? It seems that it might be ignoring the requirement that the same letter not be used more than once. – Yuval Filmus Aug 26 '18 at 2:23
• Do the words we are looking for have to be in a 'line' as in a word search? If that was the case, then assuming you can go diagonal, up-down, left-right, it would be of order equal to that of the length of the word (in your case 4), giving overall O(MNlen). It is more complicated if the word does not have to be in a line. – Alerra Aug 26 '18 at 6:07
• I've edited the question to contain the exact problem description and solution. The answer doesn't have to be in a line, but you can't move in diagonal directions, only up, down, left, and right. A simple DFS doesn't work as in a DFS you would only visit each character once. – mcfroob Aug 27 '18 at 3:34
• Code is off-topic here, so it'd be helpful if you could replace the code with concise pseudocode. Also, saying "Assume we use a DFS" seems misleading if, as you seem to say in your comment, you aren't using standard DFS. So in addition to replacing the code with concise pseudocode, it might also be helpful to read over your question and remove any statements that are inaccurate (if any). – D.W. Aug 27 '18 at 4:52

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})$.