79. Word Search

79. Word Search

time is O(m * n * 4 ^ len)

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        if (m == 0) {
            return false;   
        }
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n)); 

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (helper(board, visited, i, j, word, 0)) { // 0 is current index in word we are finding
                    return true;
                }
            }
        }
        return false;
    }
private:
    bool helper(vector<vector<char>>& board, vector<vector<bool>>& visited, int row, int col, string& word, int start) {
        if (start == word.length()) { //done
            return true;
        }
        //not done yet
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || visited[row][col] || board[row][col] != word[start]) {
            return false;
        } 
        
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        visited[row][col] = true;
        for (auto dir : dirs) {
            if (helper(board, visited, row + dir[0], col + dir[1], word, start + 1))
                return true;
        }
        visited[row][col] = false;
        return false;
    }
};

memory can be optimized by replacing visitd with input board. In other words, modifying input memory. Now memory is from call stack, which is the depth of search, O(len)

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (helper(board, i, j, word, 0)) { // 0 is current index in word we are finding
                    return true;
                }
            }
        }
        return false;
    }
private:
    bool helper(vector<vector<char>>& board, int row, int col, string& word, int start) {
        if (start == word.length()) { //done
            return true;
        }
        //not done yet
        if (row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != word[start]) {
            return false;
        } 
        
        vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        char tmp = board[row][col];
        board[row][col] = '#';
        for (auto dir : dirs) {
            if (helper(board, row + dir[0], col + dir[1], word, start + 1)) {
                board[row][col] = tmp;
                return true;
            }
        }
        board[row][col] = tmp;
        return false;
    }
};