773. Sliding Puzzle

class Solution {
    public int slidingPuzzle(int[][] board) {
        // BFS
        // convert board to string so that it can be compared to target
        // and to check it visited;
        String start =toString(board);
        String target="123450";
        Set<String> visited = new HashSet<>();
        
        Queue<String> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);

        int step = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-->0){
                String curr = queue.poll();
                if(curr.equals(target)) return step;
                for(String str: nextBoards(curr)){
                    if(!visited.contains(str)){
                        queue.offer(str);
                        visited.add(str);
                    }
                }
            }
            step++;
        }
        return -1;
    }
    
    private List<String> nextBoards(String board){
        List<String> boards = new LinkedList<>();
        //find the index of 0
        int index = board.indexOf("0");
        int i=index/3;
        int j=index%3;
        if(i-1>=0) boards.add(nextString(board, index, index-3));
        if(i+1<=1) boards.add(nextString(board, index, index+3));
        if(j-1>=0) boards.add(nextString(board, index, index-1));
        if(j+1<=2) boards.add(nextString(board, index, index+1));
        
        return boards;
    }
    
    private String nextString(String s, int index1, int index2){
        char[] chars = s.toCharArray();
        char temp=chars[index1];
        chars[index1]=chars[index2];
        chars[index2]=temp;
        return new String(chars);
    }
    
    private String toString(int[][] board){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<6; i++){
            int row = i/3;
            int col = i%3;
            sb.append(board[row][col]);
        }
        return sb.toString();
    }
}