Word Search in LeetCode

Question

I solved this programming challenge:

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.

For example,

Given board =

[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED", -> returns true

word = "SEE", -> returns true

word = "ABCB", -> returns false

class Solution {
public:
  bool DFS(vector<vector<char>> &board, string word,
           vector<vector<bool>> visited, int i, int j, int curr) {
    if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
      return false;
    }
    if (visited[i][j] || board[i][j] != word[curr]) {
      return false;
    }
    visited[i][j] = true;
    ++curr;
    if (curr == word.size()) {
      return true;
    }

    return DFS(board, word, visited, i + 1, j, curr) || // Down
           DFS(board, word, visited, i, j + 1, curr) || // Right
           DFS(board, word, visited, i - 1, j, curr) || // Up
           DFS(board, word, visited, i, j - 1, curr);   // Left
  }

  bool exist(vector<vector<char>> &board, string word) {
    for (int i = 0; i < board.size(); ++i) {
      for (int j = 0; j < board[i].size(); ++j) {
        if (word[0] == board[i][j]) {
          vector<vector<bool>> visited(board.size(),
                                       vector<bool>(board[0].size(), false));
          if (DFS(board, word, visited, i, j, 0)) {
            return true;
          }
        }
      }
    }
    return false;
  }
};

My solution ranks at around 2% faster when compared to other solutions with the same language. My main desire from reviews are performance improvements.

Answer 1

In 'exist' function, instead of looping through the entire board every time for the first character match, you can build a lookup map with char vs it's indices in the board. I modified your exist method as below and I could see better performance.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution {
  public:
   bool DFS(vector<vector<char>> &board, string word, vector<vector<bool>> visited, int i, int j, int curr) 
   {
          if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
              return false;
          }
          if (visited[i][j] || board[i][j] != word[curr]) {
             return false;
          }
          visited[i][j] = true;
          ++curr;
          if (curr == word.size()) {
             return true;
          }

          return DFS(board, word, visited, i + 1, j, curr) || // Down
                 DFS(board, word, visited, i, j + 1, curr) || // Right
                 DFS(board, word, visited, i - 1, j, curr) || // Up
                 DFS(board, word, visited, i, j - 1, curr);   // Left
    }

    void buildFirstCharIndexMap(const vector<vector<char>> &board)
    {
         firstCharIndex.clear();
         for (int i=0; i<board.size(); ++i){
             for (int j=0; j<board[i].size(); ++j){
                  firstCharIndex.emplace(make_pair(board[i][j], make_pair(i,j)));
             }
         }
    }

    bool exist (vector<vector<char>> &board, string word) {
        // get the indices for the first character.
        auto range_itr = firstCharIndex.equal_range(word[0]);

        for (auto it = range_itr.first; it != range_itr.second; ++it){
             auto cur_index_pair = it->second;

              vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));
              if (DFS(board, word, visited, cur_index_pair.first, cur_index_pair.second, 0)) {
                    return true;
              }
         }
         return false;
     }
  private:
     // lookup table for each char and it's location in the board
     multimap<char, pair<int, int>> firstCharIndex;
  };

  int main() {
       vector<vector <char>> board = {
                                  {'A','B','C','E'},
                                  {'S','F','C','S'},
                                  {'A','D','E','E'}
                                };
       Solution s;
       // build the look up table 
       s.buildFirstCharIndexMap(board);
       cout << s.exist(board, "SEE") << endl;
       cout << s.exist(board, "ABCCED") << endl;
       cout << s.exist(board, "ADCB") << endl;
       return 0;
    }