It’s great after a long day of work coming home to a cool Leetcode July Challenge. Today’s challenge is a little more difficult than we’ve had so far, but that makes for an interesting algorithm! For this problem, we’re given a 2d board of characters and a string and asked to return a boolean value indicating whether the string can be found in the 2d grid by connecting a series of adjacent characters, where an adjacent character can be up, down, left, or right of the previous character without reusing any character. We’re also given a few useful constraints:

  1. The 2d board and the search string will consist of only upper and lowercase English letters.
  2. The board height and width will be in the range [1, 200].
  3. The search word length will be in the range [1, 10^3].

Just to clarify the meaning of a word being composed of adjacent board characters, we should look at an example.

2d board:
[n,d,z,e,t]
[b,g,p,l,f]
[q,r,m,e,c]
[t,b,a,x,y]
word: "example"
algorithm path:
[n,d,z,7,t]
[b,g,5,6,f]
[q,r,4,1,c]
[t,b,3,2,y]
returns: true

From the example, it looks like we’d well served by a depth-first search algorith. The interesting bit is figuring out how to prevent our depth first search from revisiting, or rather reusing, a character that has already been visited. This particular type of depth-first search is called a backtracking algorithm. In a backtracking algorithm, it’s imporant to have a mechanism to indicate whether a particular node or element has been visited or not at a given stage of the search. This means not only marking elements as visited on the way down a path, but also unmarking them as we backtrack up the path to the last known good path. While I usually avoid recursive approaches, for this particular type of problem I really like recursion. The recursion stack is able to handle the pushing and popping of a complex function state much more easily than the iterative approach which would require several stack data structures at minimum to achieve the same functionality. I’ll probably revisit this problem at some point to explicate an iterative approach, but the clear solution here is a recursive algorithm. There’s not much in the way of edge cases for this problem except maybe single character words, words that use every character, and words not found, but the general algorithm addresses all these cases sufficiently with requiring special handling.

So, we’ll search the 2d array for the search words beginning character. When the beginning character is found, we’ll begin a backtracking depth-first search from that cell to the up-down-left-right cells. The part worth noticing is the simplicity of the backtracking control where we store a cell’s value in the stow variable, set the cell to an invalid character, ‘#’, and restore the cell after that cell’s levels of recursion return.

bool exist(vector<vector<char>>& board, string word) {
   // iterate through the array
   for(int i=0;i<board.size();i++) {
	  for(int j=0;j<board[0].size();j++) {
		 // find the starting char of word and initiate dfs
		 if(board[i][j] == word[0] && dfs(board, i, j, word)) {
			return true;
		 }
	  }
   }
   return false;
}

bool dfs(vector<vector<char>>& board, int i, int j, string word) {
   // base cases:
   // all chars in word found
   if(word.length() == 0) return true;
   // i or j out of bounds
   if(i < 0 || j < 0 || i>=board.size() || j>= board[0].size()) return false;
   // wrong character at coords
   if(board[i][j] != word.front()) return false;
   // store the current board value and set to an invalid char
   auto stow = board[i][j];
   board[i][j] = '#';
   // trim the word
   word = word.substr(1);
   // recurse to adjacent cells
   bool substringFound = dfs(board, i-1, j, word) || dfs(board, i+1, j, word) 
			    || dfs(board, i, j-1, word) || dfs(board, i, j+1, word);
   // restore the original board value
   board[i][j] = stow;
   return substringFound;
}

And that’s just good fun. Let me know if you have any recommendations for improvements on this algorithm as it’s still somewhat in flux in my mind. Check back tomorrow for more July challenge excitement!