# 79 - Word Search

解法一 - Backtracking

解法一算是比較直觀，我們可以從每個點開始做 backtracking，只要有任何一點可以走出 word 這個字，就回傳 true。

這題的終止條件比較複雜：

1. 走到超過邊界

2. 走到已經用過的 letter

3. tmp 已經跟 word 長得不一樣

實作如下：

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

        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(helper(board, word, used, tmp, i, j))
                    return true;
            }
        }

        return false;
    }

private:
    bool helper(vector<vector<char>>& board, string& word, vector<vector<bool>>& used, string& tmp, int r, int c) {
        if(tmp == word)
            return true;

        if(r<0 || r>=board.size() || c<0 || c>=board[0].size()
           || used[r][c] || (!tmp.empty() && tmp.back() != word[tmp.size()-1]))
            return false;

        used[r][c] = true;
        tmp.push_back(board[r][c]);
        if( helper(board, word, used, tmp, r-1, c) || 
            helper(board, word, used, tmp, r+1, c) ||
            helper(board, word, used, tmp, r, c-1) ||
            helper(board, word, used, tmp, r, c+1))
             return true;
        tmp.pop_back();
        used[r][c] = false;

        return false;
    }
};

Runtime: 52 ms, faster than 57.87% of C++ online submissions for Word Search. Memory Usage: 10.8 MB, less than 72.19% of C++ online submissions for Word Search.

解法二 - 優化解法一，直接修改 board 而不要額外用 used

我們其實可以透過直接修改 board 的值來當作已經走過的標示，就可以省下用額外的空間。實作如下：

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

        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(helper(board, word, tmp, i, j))
                    return true;
            }
        }

        return false;
    }

private:
    bool helper(vector<vector<char>>& board, string& word, string& tmp, int r, int c) {
        if(tmp == word)
            return true;

        if(r<0 || r>=board.size() || c<0 || c>=board[0].size()
           || board[r][c] == '\0' || (!tmp.empty() && tmp.back() != word[tmp.size()-1]))
            return false;

        char cur = board[r][c];
        tmp.push_back(cur);
        board[r][c] = '\0';
        if( helper(board, word, tmp, r-1, c) || 
            helper(board, word, tmp, r+1, c) ||
            helper(board, word, tmp, r, c-1) ||
            helper(board, word, tmp, r, c+1))
             return true;
        tmp.pop_back();
        board[r][c] = cur;

        return false;
    }
};

Runtime: 40 ms, faster than 61.84% of C++ online submissions for Word Search. Memory Usage: 10.2 MB, less than 83.75% of C++ online submissions for Word Search.