Using backtrack to solve the Word Search problem
79. Word Search
2 min readOct 7, 2021
It is a very classical problem which can be solved by backtracking.
Naive backtracking
typedef pair<int, int> PII;
const vector<PII> dirs = {{0, 1},{0, -1},{1, 0},{-1, 0}};
int seen[10][10];
class Solution {
public:
string word;
vector<vector<char>> board;
int n, m;
bool backtrack(vector<PII>& candidates, int k)
{
if (k == word.size()) return true;
for (auto& [i, j]: candidates){
if (seen[i][j]) continue;
seen[i][j] = 1;
vector<PII> new_candidates;
for (auto &[di, dj]: dirs){
int r = i + di, c = j + dj;
if (r >= 0 && r < n && c >=0 && c < m && board[r][c] == word[k+1]){
new_candidates.emplace_back(r, c);
}
}
if (backtrack(new_candidates, k + 1)){
return true;
}
seen[i][j] = 0;
}
return false;
}
bool exist(vector<vector<char>>& board, string word) {
const int n = board.size(), m = board[0].size();
this-> word = word;
this-> board = board;
this -> n = n; this -> m = m;
// use vector got TLE
//vector<vector<int>> seen(n, vector<int>(m, 0));
memset(seen, 0, sizeof seen);
if (word.empty())return true;
vector<PII> candidates;
for (int i = 0; i < n; ++i){
for (int j = 0; j < m; ++j){
if (board[i][j] == word[0]){
candidates.emplace_back(i, j);
}
}
}
if (candidates.empty()) return false;
return backtrack(candidates, 0);
}
};Run time
Runtime: 1912 ms, faster than 5.02% of C++ online submissions for Word Search.Memory Usage: 289.5 MB, less than 5.08% of C++ online submissions for Word Search.
A better way
We can also update the explored value to an obviously invalid character to not use the seen.
class Solution {
public:
vector<vector<char>> board;
string word;
bool backtrack(int i, int j, int k)
{
if (i<0 || i>=board.size() || j<0 || j>=board[0].size())return false;
if(board[i][j]!=word[k])return false;
if (k==word.length()-1)return true;
auto original_val = board[i][j];
board[i][j] = '#';
if(backtrack(i-1, j, k+1) ||
backtrack(i, j-1, k+1) ||
backtrack(i+1, j, k+1) ||
backtrack(i, j+1, k+1)) return true;
board[i][j] = original_val ;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
const int R = board.size(), C = board[0].size();
this -> board = board;
this -> word = word;
for(int i = 0;i<R;++i)
for(int j =0;j<C;++j)
if(backtrack(i, j, 0))return true;
return false;
}
};This version is faster
Runtime: 204 ms, faster than 85.62% of C++ online submissions for Word Search.Memory Usage: 7.5 MB, less than 19.78% of C++ online submissions for Word Search.
Time complexity analysis
I believe there is a tighter bound. I conclude the runtime is O(n² * 4 * 3^(k-1)) = O(n² * 3^k).
Explanation: We start the word search over all n² nodes. For the first letter of the word search we can move in 4 directions but for every later one there are only three options (you can’t move back onto yourself. From [1]
