C++LeetCode 구현(79.단어 검색)

[LeetCode]79.단어 검색 어 검색
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 cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
["ABCE"],
["SFCS"],
["ADEE"]
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
이 문 제 는 전형 적 인 깊이 가 DFS 를 우선 적 으로 옮 겨 다 니 는 응용 프로그램 입 니 다.원래 2 차원 배열 은 하나의 미로 와 같 습 니 다.상하 좌우 네 방향 으로 걸 을 수 있 습 니 다.우 리 는 2 차원 배열 의 모든 수 를 기점 으로 주어진 문자열 과 일치 합 니 다.우 리 는 원 배열 등 크기 의 visited 배열 이 필요 합 니 다.bool 형 으로 현재 위치 가 방문 되 었 는 지 기록 해 야 합 니 다.제목 때문에 한 cell 에 한 번 만 접근 할 수 있 습 니 다.2 차원 배열 board 의 현재 문자 와 대상 문자열 word 에 대응 하 는 문자 가 같 으 면 상하 좌우 네 개의 인접 문자 에 대해 각각 DFS 의 재 귀 함 수 를 호출 합 니 다.트 루 로 돌아 가 는 것 이 있 으 면 해당 하 는 문자열 을 찾 을 수 있 음 을 나타 냅 니 다.그렇지 않 으 면 찾 을 수 없습니다.구체 적 으로 코드 를 보면 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j, vector<vector<bool>>& visited) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || board[i][j] != word[idx]) return false;
        visited[i][j] = true;
        bool res = search(board, word, idx + 1, i - 1, j, visited) 
                 || search(board, word, idx + 1, i + 1, j, visited)
                 || search(board, word, idx + 1, i, j - 1, visited)
                 || search(board, word, idx + 1, i, j + 1, visited);
        visited[i][j] = false;
        return res;
    }
};

우 리 는 visited 배열 을 사용 하지 않 고 board 배열 을 직접 수정 할 수 있 습 니 다.옮 겨 다 니 는 위 치 를 우물 번호 로 바 꿀 수 있 습 니 다.재 귀적 으로 사용 한 후에 이전의 상 태 를 회복 해 야 합 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.empty() || board[0].empty()) return false;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (search(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }
    bool search(vector<vector<char>>& board, string word, int idx, int i, int j) {
        if (idx == word.size()) return true;
        int m = board.size(), n = board[0].size();
        if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] != word[idx]) return false;    
        char c = board[i][j];
        board[i][j] = '#';
        bool res = search(board, word, idx + 1, i - 1, j) 
                 || search(board, word, idx + 1, i + 1, j)
                 || search(board, word, idx + 1, i, j - 1)
                 || search(board, word, idx + 1, i, j + 1);
        board[i][j] = c;
        return res;
    }
};

C++구현 LeetCode(79.단어 검색)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 단어 검색 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부 탁 드 리 겠 습 니 다!