Java BFS solution


  • 1

    For each iteration, we find all the possible ways to insert a ball according to the current state.

    public class Solution {
        Map<Character, Integer> colorId = new HashMap<>();
        
        public int findMinStep(String board, String hand) {
            String color = "RYWBG";
            List<Integer> handBall = new ArrayList<>(Arrays.asList(0,0,0,0,0));
            int index = 0;
            for(char c : color.toCharArray()){
                colorId.put(c, index ++);
            }
            
            for(char ball : hand.toCharArray()){
                handBall.set(colorId.get(ball), handBall.get(colorId.get(ball)) + 1);
            }
    
            return BFS(new StringBuilder(board), handBall);
        }
        
        public int BFS(StringBuilder board, List<Integer> handBall){
            Queue<State> queue = new LinkedList<>();
            Set<String> nextBoardSet = new HashSet<>();
            queue.offer(new State(board, handBall));
            int ans = 0;
            while(!queue.isEmpty()){
                int size = queue.size();
                ans ++;
                while(size -- > 0){
                    State currentState = queue.poll();
                    StringBuilder currentBoard = currentState.board;
                    List<Integer> currentHandBall = currentState.handBall;
                    
                    for(int start = 0, end = start + 1; start < currentBoard.length(); start = end, end++){
                        while(end < currentBoard.length() && currentBoard.charAt(end) == currentBoard.charAt(end - 1)){
                            end ++;
                        }
                        int number = end - start;
                        int colorIndex = colorId.get(currentBoard.charAt(start));
                        if(currentHandBall.get(colorIndex) < 3 - number){
                            continue;
                        }
                        else{
                            StringBuilder nextBoard = new StringBuilder(currentBoard.toString());
                            if(number == 2){
                            	nextBoard.delete(start, end);
                            	nextBoard = reduce(nextBoard);
                                if(nextBoard.length() == 0){
                                    return ans;
                                }
                            }
                            else{
                            	nextBoard.insert(end, currentBoard.charAt(start));
                            }
                            if(!nextBoardSet.add(nextBoard.toString())){
                                continue;
                            }
                            
                            List<Integer> nextHandBall = new ArrayList<>();
                            nextHandBall.addAll(currentHandBall);
                            nextHandBall.set(colorIndex, nextHandBall.get((colorIndex)) - 1);
                            queue.offer(new State(nextBoard, nextHandBall));
                        }
                    }
                }
            }
            return -1;
        }
        
        public StringBuilder reduce(StringBuilder nextBoard){
            String board = nextBoard.toString();
            String tmp = board.replaceAll("([RYBGW])\\1{2,}","");
            while (tmp.length() != board.length()) {
                board = tmp;
                tmp = board.replaceAll("([RYBGW])\\1{2,}","");
            }
            return new StringBuilder(tmp);
        }
        
    }
    
    class State {
        StringBuilder board;
        List<Integer> handBall = new ArrayList<>();
        
        public State(StringBuilder board, List<Integer> handBall){
            this.board = board;
            this.handBall = handBall;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.