題目
給定一個二維網(wǎng)格和一個單詞知态，找出該單詞是否存在于網(wǎng)格中。
單詞必須按照字母順序出革，通過相鄰的單元格內(nèi)的字母構(gòu)成叠萍，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格悲敷。同一個單元格內(nèi)的字母不允許被重復使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
給定 word = "ABCCED", 返回 true.
給定 word = "SEE", 返回 true.
給定 word = "ABCB", 返回 false.
思路
使用DFS遍歷矩陣俭令，直到遍歷完字符串后德，說明匹配。但是需要記錄矩陣中哪個字符是已經(jīng)匹配過的抄腔。
由于英文字符范圍是0~127瓢湃，因此遍歷某個字符后，進行c^=128操作赫蛇，該字符在后續(xù)匹配中就不會再次匹配到绵患，從而實現(xiàn)標記的效果。在回溯的時候需要將標記的字符還原悟耘。
#include<vector>
using namespace std;
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int rows = board.size(), cols = board[0].size();
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if (findWord(board, word, i, j, 0))
return true;
}
}
return false;
}
bool findWord(vector<vector<char>> board, string word, int row, int col, int index)
{
if (index == word.size()) return true;
if (row < 0 || col < 0 || row >= board.size() || col >= board[0].size() || board[row][col] != word.at(index))
return false;
board[row][col] ^= 128;
bool exist = findWord(board, word, row - 1, col, index + 1) ||
findWord(board, word, row, col - 1, index + 1) ||
findWord(board, word, row + 1, col, index + 1) ||
findWord(board, word, row, col + 1, index + 1);
board[row][col] ^= 128;
return exist;
}
};
int main(int argc, char* argv[])
{
vector<vector<char>> test = {
{ 'A','B','C','E' },
{ 'S','F','C','S' },
{ 'A','D','E','E' } };
vector<vector<char>> test2 = {
{ 'A' },
{ 'B'} };
string word1 = "ABCCED", word2 = "SEE", word3 = "BA";
auto res = Solution().exist(test2, word3);
return 0;
}
