Word Search

<-M 79> Word Search

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

        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(dfs(board, word, 0, i, j, visited))
                    return true;
        return false;
    }
private:
    bool dfs(const vector<vector<char>>& board, const string word,
             int index, int x, int y, vector<vector<bool>>& visited) {
        if(index == word.size())
            return true;
        if(x < 0 || y < 0 || x >= board.size() || y >= board[0].size())
            return false;

        if(visited[x][y])
            return false;

        if(board[x][y] != word[index])
            return false;

        visited[x][y] = true;
        bool ret = dfs(board, word, index + 1, x - 1, y, visited) ||
                    dfs(board, word, index + 1, x + 1, y, visited) ||
                    dfs(board, word, index + 1, x, y + 1, visited) ||
                    dfs(board, word, index + 1, x, y - 1, visited);
        visited[x][y] = false;
        return ret;
    }
};

// Method 2
class Solution {
    bool find(vector<vector<char>>& board, std::string const& word, int row, int col, std::string prefix) {
        if (row < 0 || row >= board.size())
            return false;

        if (col < 0 || col >= board[0].size())
            return false;

        constexpr char VISITED_CELL = '#';

        char& cell = board[row][col];

        char const ch = cell;

        if (ch == VISITED_CELL)
            return false;

        if (word.compare(0, prefix.length(), prefix) != 0)
            return false;

        prefix.push_back(ch);

        if (prefix.length() == word.length())
            return prefix == word;

        cell = VISITED_CELL;

        if (find(board, word, row - 1, col, prefix)) return true;
        if (find(board, word, row, col + 1, prefix)) return true;
        if (find(board, word, row + 1, col, prefix)) return true;
        if (find(board, word, row, col - 1, prefix)) return true;

        cell = ch;

        prefix.pop_back();

        return false;
    }

public:

    bool exist(vector<vector<char>>& board, string word) {
        if (word.empty())
            return true;

        std::unordered_map<char, int> charCount;
        for (char ch : word)
            charCount[ch]++;

        char const firstChar = word.front();
        char const lastChar = word.back();

        std::vector<std::pair<int, int>> startingLocations, startingLocationsReverse;
        for (int row = 0; row < board.size(); ++row) {
            for (int col = 0; col < board[0].size(); ++col) {
                char const ch = board[row][col];

                auto it = charCount.find(ch);
                if (it != std::end(charCount))
                    it->second--;

                if (firstChar == ch)
                    startingLocations.emplace_back(row, col);

                if (lastChar == ch)
                    startingLocationsReverse.emplace_back(row, col);
            }
        }

        for (auto const& [ch, count] : charCount) {
            if (count > 0)
                return false;
        }

        auto& locations = startingLocations;

        if (startingLocationsReverse.size() < startingLocations.size()) {
            std::reverse(std::begin(word), std::end(word));
            locations = startingLocationsReverse;
        }

        for (auto const& [row, col] : locations) {
            if (find(board, word, row, col, ""))
                return true;
        }

        return false;
    }
};