Word Search

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

Word Search - LeetCode

 

주어진 보드의 문자를 연결해서 타겟으로 하는 문자열이 존재하는지 체크하는 문제이다.
기본적인 DFS 백트래킹으로 문제를 풀 수 있다. 보드의 상하좌우 탐색, 방문 체크, 조건 체크와 boolean 값 리턴 등에서 오류가 나지 않게 처리해주면 무난히 풀 수 있었다. 최종 코드는 아래와 같다.

public class Solution {  
  
    int[] dr = {1, 0, -1, 0};  
    int[] dc = {0, 1, 0, -1};  
    boolean[][] visited;  
  
    public boolean exist(char[][] board, String word) {  
        int m = board.length;  
        int n = board[0].length;  
        visited = new boolean[m][n];  
  
        for(int i = 0; i < m; i++){  
            for(int j = 0; j < n; j++){  
                if(board[i][j] == word.charAt(0)){  
                    visited[i][j] = true;  
                    if(dfs(board, i, j, 0, word)){  
                        return true;  
                    };  
                    visited[i][j] = false;  
                }  
            }  
        }  
  
        return false;  
    }  
  
    private boolean dfs(char[][] board, int r, int c, int idx, String word){  
        if(idx == word.length() - 1){  
            return true;  
        }  
  
        if(idx > word.length() - 1){  
            return false;  
        }  
  
        int nextIdx = idx + 1;  
        for(int dir = 0; dir < 4; dir++){  
            int nextRow = r + dr[dir];  
            int nextCol = c + dc[dir];  
            if(nextRow >= 0 && nextRow < board.length  
                    && nextCol >= 0 && nextCol < board[0].length  
                    && !visited[nextRow][nextCol]  
                    && board[nextRow][nextCol] == word.charAt(nextIdx)  
            ){  
                visited[nextRow][nextCol] = true;  
                if(dfs(board, nextRow, nextCol, nextIdx, word)){  
                    return true;  
                };  
                visited[nextRow][nextCol] = false;  
            }  
        }  
  
        return false;  
    }  
}

 

같은 형태로 문자열 배열을 체크하는 문제가 있었는데 해당 문제는 상당히 어려웠었다. 이 문제를 해결한 이후 Trie 자료구조 알고리즘을 공부했다면 도전할 만 하다.

 

https://ygs3004.tistory.com/93

Word Search II