[C++] Leetcode : Word Search

Question

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.

Follow up: Could you use search pruning to make your solution faster with a larger board?

 

문자판의 m x n 그리드와 문자열 단어가 주어질 때 단어가 그리드에 있으면 true를 반환합니다.

단어는 인접 셀이 수평 또는 수직으로 인접하는 순차적으로 인접한 셀의 문자로 구성될 수 있습니다. 동일한 문자 셀은 두 번 이상 사용할 수 없습니다.

 

제약사항

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

---

Solution 1

바로 BFS Serach를 하면 될 것 같다. 다른 방법은 바로 떠오르진 않는다. 
+) 
코드를 작성하다 보니, BFS search로 하면 visited 처리가 어려울 것 같다. DFS로 틀어야 할 것 같다. 

class Solution {
public:
bool exist(vector<vector<char>>& board, string word, int row, int col, int i) {
        if (i >= word.size()) {
            return true;
        }

        if (row >= board.size() || col >= board[0].size() || row < 0 || col < 0 || board[row][col] == '-') {
            return false;
        }

        if (word[i] == board[row][col]) {
            char ch = board[row][col];
            board[row][col] = '-';
            bool down = exist(board, word, row + 1, col, i + 1);
            bool right = exist(board, word, row, col + 1, i + 1);
            bool left = exist(board, word, row - 1, col, i + 1);
            bool up = exist(board, word, row, col - 1, i + 1);

            if (down || right || left || up) {
                return true;
            }
            board[row][col] = ch;
        }
        
        return false;

    }
    bool exist(vector<vector<char>>& board, string word) {

        int row = board.size(), col = board[0].size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (exist(board, word, i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
};