public boolean exist2Rec(char[][] board, String word, int pos, int i, int j){
        if(pos == word.length()) return true;
        if(isValidIdx(i, j) && !visited[i][j] && pos < word.length() && board[i][j] == word.charAt(pos)){
            visited[i][j] = true;
            if(exist2Rec(board, word, pos+1, i-1, j)) return true;
            if(exist2Rec(board, word, pos+1, i+1, j)) return true;
            if(exist2Rec(board, word, pos+1, i, j-1)) return true;
            if(exist2Rec(board, word, pos+1, i, j+1)) return true;
            visited[i][j] = false;
        }
        return false;
    }