4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Should you not reset the visited value after the dfs returns? For example if the input is {"AB","BC","DE"} and the string to be searched is "ABCBD" does it find it correctly? \$\endgroup\$ – Raziman T V Feb 9 '17 at 19:02
  • \$\begingroup\$ @RazimanTV, visited is passed by value, it should be correct. \$\endgroup\$ – Incomputable Feb 9 '17 at 19:08
  • \$\begingroup\$ @Incomputable Yes, that's why it is correct. Although I believe this might also cause a performance hit. \$\endgroup\$ – thebenman Feb 9 '17 at 19:10
  • \$\begingroup\$ Ah yes, missed it. Then the obvious performance improvement would be to pass by reference and deal with undoing it properly. \$\endgroup\$ – Raziman T V Feb 9 '17 at 19:16
  • 1
    \$\begingroup\$ @RazimanTV, I'll make a wild guess here, but I think that only amount of comparisons matter here. Since the solution didn't overflow the stack, it is possible that the data set or the string is small, so copying should be almost free (well, if std::vector<bool> uses memcpy() and has small object optimization). If it allocates something on the heap, then certainly it will have considerable impact. \$\endgroup\$ – Incomputable Feb 9 '17 at 19:20
2
\$\begingroup\$

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;
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.