[leetcode 79] Word Search

Given a 2D 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.

 

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

 

Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

처음 접근:

- bfs => 실패. 한번 지나간 문자에 대해 중복 체크가 불가능하기 때문

- 백트래킹이 필요

class Solution {
public:
    
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1,-1, 0, 0};
    bool visited[201][201];
    
    bool isValid(int row, int col, int n, int m){
        if(row > n-1 || row < 0 || col <0 || col > m-1){
            return false;
        }
        return true;
    }
   
    bool DFS(int row, int col, int tmp, vector<vector<char>>& board, string& word){
        
        if(!isValid(row, col, board.size(), board[0].size())){
            return false;
        }
        
        if(visited[row][col]){
            return false;
        }
        
        if(tmp == word.length()-1 && board[row][col] == word[tmp]){
            return true;
        }
        
        
        if(board[row][col] != word[tmp]){
            return false;
        }
        for(int i=0; i<4; i++){
            int nextRow = row + dx[i];
            int nextCol = col + dy[i];
            
            visited[row][col] = true;
            if(DFS(nextRow, nextCol, tmp+1, board, word)){
                return true;
            }
            visited[row][col] = false;
        }
        return false;
    }
    
    bool exist(vector<vector<char>>& board, string word) {
        
        for(int i=0; i<board.size(); i++){
            for(int j=0; j<board[0].size(); j++){
                if(board[i][j] == word[0]){
                    memset(visited, false, sizeof(visited));
        
                    if(DFS(i,j,0,board,word)){
                        return true;
                    }
                }
                
            }
        }
        return false;
    }
};