[LeetCode] 79. Word Search

https://leetcode.com/problems/word-search/description/

Leetcode - Word Search

문제 유형 : 문자열 처리, dfs, 백트래킹

문제 난이도 : Medium

 

문제

Given an m x n grid of characters board and a string word, return true if 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.

 

문자열 word와 m * n의 2차원배열 board가 주어진다. board에 word를 찾을 수 있는지 반환하시오.

단어는 상하좌우로 인접한 문자끼리 접합하여 만들 수 있습니다.

 

풀이

dfs + 백트래킹으로풀 수 있다.

 

재귀함수() {

    if(단어 완성) 종료

    visited[x][y] = true

    // 인접한 문자들 중, 접합시킬 수 있다면 재귀로 들어감

    visited[x][y] = false

}

의 형태로 구현하면 된다.

 

 

코드

C++

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

class Solution {
private:
    bool found;
    int n;
    int m;
public:
    void search(vector<vector<char>>& board, vector<vector<bool>>& visited, string word, int x, int y, int idx) {
        visited[x][y] = true;
        if(idx >= word.size()) {
            found = true;
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(visited[nx][ny]) continue;

            if(word[idx] == board[nx][ny]) {
                search(board, visited, word, nx, ny, idx+1);
            }
        }

        visited[x][y] = false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        vector<vector<bool>> visited (n, vector<bool>(m, false));
        found = false;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(board[i][j] == word[0]) {
                    search(board, visited, word, i, j, 1);
                    if(found) return true;
                }
            }
        }

        return false;
    }
};