[LeetCode] Word Search (Medium)

LeetCode

[LeetCode] Word Search (Medium)

[풀이]

 

크기가 (3,5)인 2차원 배열에서 word="ABCHM" 를 찾는 경우

예시

결론: 찾고자 하는 word="ABCHM" 를 DFS로 사용해서 찾는다.

 

2차원 배열의 (0,0)부터 (2, 4)까지 반복문을 수행한다.

 

모든 위치를 시작점으로 word의 첫 글자와 일치하는 경우 dfs를 시도한다.

public class Word_Search {
    public boolean exist(char[][] board, String word) {
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                if(board[i][j] == word.charAt(0) 
                   && dfs(i,j,1,board,word)){
                   return true;
                }
            }
        }
        return false;
    }
    static int[] dx={1,0,-1,0};
    static int[] dy={0,1,0,-1}; 
    public static boolean dfs(int x, int y, int idx, char[][] board, String word){
        if(idx == word.length()){
            return true;
        }
        
        char temp = board[x][y];
        board[x][y] = '\0';
        for(int d=0; d<4; d++){
            int nx = x + dx[d];
            int ny = y + dy[d];
            if(nx<0 || nx>=board.length || ny<0 || ny>=board[0].length) 
                continue;
            if(board[nx][ny] == word.charAt(idx) && dfs(nx,ny,idx+1,board,word))
                return true;
        }
        board[x][y] = temp;
        return false;
    }
}