Leetcode - 79. Word Search

문제

char타입 2차원 배열에 문자가 포함되어있다. 주어지는 word와 일치하는 연속된 문자열이 존재하는지 파악하라. 단 상하좌우 방향 관계없음. 중복된 문자를 지날 수 없음.

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], 
word = "ABCCED"
Output: true

해결

DFS 그리고 Visited 로 가지치기(pruning)하여 풀 수 있는 문제.

class Solution {
    string w;
    int rsize;
    int csize;
    int **visit;
    
    bool check_str(vector<vector<char>>& board, int i, int j, int widx, int size)
    {
        /* base case */
        if (i < 0 || i >= rsize || j < 0 || j >= csize)
            return false;
        if (size < 0)
            return false;
        if (visit[i][j])
            return false;
        if (w[widx] != board[i][j])
            return false;

        if (size == 0)
            return true;
        
        /* visited */
        visit[i][j] = 1;

        /* recursion */
        if (check_str(board, i + 1, j, widx + 1, size - 1))
            return true;
        if (check_str(board, i, j + 1, widx + 1, size - 1))
            return true;
        if (check_str(board, i - 1, j, widx + 1, size - 1))
            return true;
        if (check_str(board, i, j - 1, widx + 1, size - 1))
            return true;
        
        visit[i][j] = 0;
        
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        w = word;
        rsize = board.size();
        csize = board[0].size();
        visit = new int *[rsize]{0};
        for (int i = 0; i < rsize; i++)
            visit[i] = new int[csize]{0};
        
        
        for (int i = 0; i < rsize; i++) {
            for (int j = 0; j < csize; j++) {
                if (board[i][j] != word[0])
                    continue;
                if (check_str(board, i, j, 0, word.size() - 1))
                    return true;
            }
        }
        return false;
    }
};