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.

• Raziman T V: 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?
• Incomputable: @RazimanTV, visited is passed by value, it should be correct.
• thebenman: @Incomputable Yes, that's why it is correct. Although I believe this might also cause a performance hit.
• Raziman T V: Ah yes, missed it. Then the obvious performance improvement would be to pass by reference and deal with undoing it properly.
• Incomputable: @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.

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;
 }