[LeetCode] 79. Word Search

Problem

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.

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:

• 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

class Solution {
    public boolean exist(char[][] board, String word) {
        for (int row = 0; row < board.length; row++)
            for (int col = 0; col < board[0].length; col++)
                if (board[row][col] == word.charAt(0) && helper(board, word, 0, row, col))
                    return true;
        return false;
    }
    private boolean helper(char[][] board, String word, int wordIndex, int row, int col){
        if (word.length() <= wordIndex)
            return true;
        
        if (row < 0 ||
            col < 0 ||
            board.length <= row ||
            board[0].length <= col ||
            board[row][col] == '0' ||
            board[row][col] != word.charAt(wordIndex))
            return false;
        
        char tmp = board[row][col];
        board[row][col] = '0';
        
        if (helper(board, word, wordIndex + 1, row + 1, col) ||
            helper(board, word, wordIndex + 1, row - 1, col) ||
            helper(board, word, wordIndex + 1, row, col + 1) ||
            helper(board, word, wordIndex + 1, row, col - 1))
            return true;
        
        board[row][col] = tmp;
        
        return false;
    }

}

Explanation

• 문자열 word의 첫 번째 글자 혹은 마지막 글자를 기준으로 배열 board을 차례로 참조하면, 한 방향으로 문자열 word를 참조할 수 있고, 배열 board에서 문자열 word의 존재를 확인할 수 있다. 이 문제에서는 문자열 word의 첫 번째 글자를 기준으로 비교를 시작하겠다.

  for (int row = 0; row < board.length; row++)
    for (int col = 0; col < board[0].length; col++)
        if (board[row][col] == word.charAt(0))
  return false;
  

• 배열 board에서 문자열 word의 첫번째 글자를 찾게되면, 문자열 word의 두번째 글자를 배열 board에서 찾아야 하는데, 총 4가지 경우의 수를 생각해야 한다.
• 4가지 경우의 수는 문자열 word의 두 번째 글자가 배열 board에서 첫 번째 글자 위쪽, 아래쪽, 왼쪽, 오른쪽에 존재하는 경우이다. 이렇게 경우의 수가 많을 때는 재귀함수를 호출하여 처리할 수 있다.
• 재귀 함수 helper()를 선언하는데, 재귀 함수 내에서 사용할 변수들을 파라미터로 작성해준다.

  private boolean helper(char[][] board, String word, int wordIndex, int row, int col)
  

• 재귀함수를 호출하는 if 조건문을 작성해준다.

  if (helper(board, word, wordIndex + 1, row + 1, col) || // 위쪽 이동
    helper(board, word, wordIndex + 1, row - 1, col) || // 아래족 이동
    helper(board, word, wordIndex + 1, row, col + 1) || // 오른쪽 이동
    helper(board, word, wordIndex + 1, row, col - 1)) // 왼쪽 이동
    return true;
  

• 지나왔던 경로는 비교에 포함되면 안되기 때문에, 지나왔던 경로에 임시로 '0'을 할당해준다.
• 처음 재귀 함수 helper()가 실행되면 문자열 word의 첫 글자와 동일한 배열 board의 요소에 '0'이 할당된다.

  char tmp = board[row][col];
  board[row][col] = '0';
  

• 재귀 함수 helper()의 결과로 false를 반환하는 경우의 수를 if 조건문으로 작성한다.

  if (row < 0 || // 위쪽 경계를 넘어가는 경우
    col < 0 || // 왼쪽 경계를 넘어가는 경우
    board.length <= row || // 오른족 경계를 넘어가는 경우
    board[0].length <= col || // 아래쪽 경계를 넘어가는 경우
    board[row][col] == '0' || // 지나왔던 경로인 경우
    board[row][col] != word.charAt(wordIndex)) // 이동하여 도착한 요소가 word의 글자와 일치하지 않는 경우
    return false;
  

• 재귀 함수 helper()의 진행 중 문자열 word의 마지막 글자까지 오게된 경우는 문자열 word가 배열 board에 존재한다는 의미가 되므로 true를 반환하도록 if 조건문을 작성한다.

  if (word.length() <= wordIndex)
    return true;
  

• 처음 작성한 for 반복문에서 재귀 함수 helper()를 실행하도록 한다.
• 재귀 함수 helper()를 진행하는 과정에서 true만 반환하면 배열 board속에 문자열 word가 존재한다는 의미가 되므로 true를 반환하도록 한다.

  for (int row = 0; row < board.length; row++)
    for (int col = 0; col < board[0].length; col++)
        if (board[row][col] == word.charAt(0) && helper(board, word, 0, row, col))
            return true;
  return false;
  

• 다음 for 반복문의 if 조건문이 실행될 걸 대비하여 임의로 '0'을 할당했던 요소들을 원래상태로 돌려놓는다.

  board[row][col] = tmp;
  

• 재귀 함수 helper의 반환 값을 지정해주어야 하는데, 재귀 함수 helper내의 if 조건문에서 true를 반환하지 못하는 경우 false를 반환하도록 한다.

  return false;