# 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.
Commented Aug 26, 2018 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. Commented Aug 26, 2018 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. Commented Aug 26, 2018 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. Commented Aug 27, 2018 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.
Commented Aug 27, 2018 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})$.

• Thanks for the comment. I think you're basically right, but instead of 4^mn, I think it should be 4^s, where s is the length of the input string. Commented Aug 28, 2018 at 4:17
• Sorry i missed one line of your code. Let me update the answer Commented Aug 28, 2018 at 8:05
• Great answer. Thanks.
– Sush
Commented Dec 29, 2019 at 21:08

I think the worst case is bound by O(n * m * 3^s), that's because we can't use a letter which we already used, therefore any node in the DFS would have 3 options and would obviously not consider the parent.

Based on Navjot's answer, I think the complexity should be $$𝑂(𝑚𝑛\times 3^s)$$, because except the first step, you can only chose from 3 directions. You cannot go back to the previous position.

For people wondering why the above algorithm is not TLE (Time Limit exceeded),

The time complexity is not O(mn*4^k) but O(mn*3^k).

Assuming m,n = 6 and k=15,

O(36*4^15) = 10^11 and O(36*3^15) = 10^8.

Anything above 10^9 is TLE which above algo doesn't exceed.