# Using backtrack to solve the Word Search problem

## 79. Word Search

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]

# Reference

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi