LeetCode: 79. Word Search
tags: LeetCode 79. Word Search class Solution { public: bool exist(vector<vector<char>>& board, string word) { backtracking(board, word, 0, 0); return res; } private: string track; bool res = false; enum Direction { right, down, up, left, }; /** * @param dir: 0: right, 1: down, 2: up, 3: left */ void backtracking(vector<vector<char>>& board, string word, int row, int col) { if (track == word || res) { res = true; return; } for (int i = row; i < board.size(); i++) { for (int j = col; j < board[i].size(); j++) { auto directions = get_next_directions(board, i, j); if (directions.size() == 0) { return; } for (auto d: directions) { int r, c; track.push_back(board[i][j]); std::tie(r, c) = next_char_pos(board, row, col, d); if (word.find(track) == 0) { backtracking(board, word, r, c); } track.pop_back(); } } } } vector<Direction> get_next_directions(vector<vector<char>>& board, int row, int col) { vector<Direction> r; if (col < board[row].size() - 1) { r.push_back(right); } if (row < board.size() - 1) { r.push_back(down); } if (row > 0) { r.push_back(up); } if (col > 0) { r.push_back(left); } return r; } tuple<int, int> next_char_pos(vector<vector<char>>& board, int row, int col, Direction dir) { switch(dir) { case right: col++; break; case left: col--; break; case up: row--; break; case down: row++; break; } tuple<int, int>r(row, col); return r; } }; 失败的用例： ...