patterncppMinor
Word Search in LeetCode
Viewed 0 times
wordleetcodesearch
Problem
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 =
word = "ABCCED", -> returns true
word = "SEE", -> returns true
word = "ABCB", -> returns 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.
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> &board, string word,
vector> visited, int i, int j, int curr) {
if (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> &board, string word) {
for (int i = 0; i > visited(board.size(),
vector(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.
Solution
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
#include
#include
using namespace std;
class Solution {
public:
bool DFS(vector> &board, string word, vector> visited, int i, int j, int curr)
{
if (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> &board)
{
firstCharIndex.clear();
for (int i=0; i> &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> visited(board.size(), vector(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> firstCharIndex;
};
int main() {
vector> 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;
}Code Snippets
#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;
}Context
StackExchange Code Review Q#154933, answer score: 2
Revisions (0)
No revisions yet.