79. Word Search
1. Description
Given an m x n board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cells, where “adjacent” cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.
2. Example
Example 1:
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCCED”
Output: true
Example 2:
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “SEE”
Output: true
Example 3:
Input: board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]], word = “ABCB”
Output: false
3. Constraints
- m == board.length
- n = board[i].length
- 1 <= m, n <= 200
- 1 <= word.length <= $10^3$
- board and word consists only of lowercase and uppercase English letters.
4. Solutions
My Accepted Solution
n is the number of letters in the board, l = word.size()
Time complexity: O($n3^l$)
Space complexity: O(l)
class Solution {
public:
bool exist(const vector<vector<char>> &board, const string &word) {
auto m_board(board);
for (int i = 0; i < m_board.size(); ++i) {
for (int j = 0; j < m_board[0].size(); ++j) {
if (_find_word(i, j, m_board, word, 0)) {
return true;
}
}
}
return false;
}
private:
bool _find_word(
const int row,
const int column,
vector<vector<char>> &m_board,
const string &word,
const int index) {
if (index == word.size()) {
return true;
} else {
if (0 <= row && row < m_board.size() && 0 <= column && column < m_board[0].size() &&
m_board[row][column] == word[index]) {
m_board[row][column] *= -1;
if (_find_word(row + 1, column, m_board, word, index + 1) ||
_find_word(row - 1, column, m_board, word, index + 1) ||
_find_word(row, column + 1, m_board, word, index + 1) ||
_find_word(row, column - 1, m_board, word, index + 1)) {
return true;
}
m_board[row][column] *= -1;
return false;
} else {
return false;
}
}
}
};