Java BFS solution encoding hand with prime numbers.


  • 0

    Since there are only 5 colors and 5 balls on hand. We can encode each color as a prime number instead of a using HashMap. Also, we only need to put the balls which have the same color with the balls on the board. If none of the ball on hand has the color on the board, than it is a "dead" game. In other words, no more next step. Because the goal is to find the "minimum" steps, using BFS should be the most appropriate approach.

    public class Solution {
        int[] colorCodes = new int[]{0,2,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,7,0,11,0};
        int getColor(char c) { return colorCodes[c-'A']; }
        int encode(String hand){
            int code=1;
            for (char c : hand.toCharArray())
                code *= getColor(c);
            return code;
        }
        class Game {
            String board;
            int hand;
            Game(String board, int hand){
                this.board= board;
                this.hand = hand;
            }
            String getKey() { return board+","+hand; }
        }
        
        String checkBoard(String board){
            if (board==null || board.length() <=2 ) return board;
            for (int i=0; i< board.length()-2; i++) {
                if (board.charAt(i) == board.charAt(i+2) && board.charAt(i) == board.charAt(i+1) ) {
                    int right = i+3;
                    while (right<board.length() && board.charAt(right)==board.charAt(i)) right++;
                    return checkBoard(board.substring(0,i) + board.substring(right));
                }
            }
            return board;
        }
        
        int BFS(String board, int hand) {
            Set<String> visited = new HashSet<>();
            Queue<Game> queue = new LinkedList<>();
            Queue<Game> nextSteps = new LinkedList<>();
            if (board.length()==0) return 0;
            if (hand == 1) return -1;
            int step = 1;
            Game ini = new Game(board, hand);
            queue.offer( ini );
            visited.add(ini.getKey());
            while (! queue.isEmpty() ) {
                Game cur = queue.poll();
                if (cur.hand > 1) {
                    for (int i=0; i<cur.board.length(); i++) {
                        int color = getColor(cur.board.charAt(i));
                        if ( (cur.hand % color) == 0 ) {
                            String next = checkBoard(cur.board.substring(0,i+1)+cur.board.substring(i));
                            if (next.length()==0) return step;
                            Game nextGame = new Game( next, cur.hand/color);    
                            if (nextGame.hand > 1 && ! visited.contains(nextGame.getKey())) {
                                nextSteps.offer( nextGame );
                                visited.add(nextGame.getKey());
                            }
                        }
                    }
                }
                if (queue.isEmpty()) {
                   step++;
                   queue=nextSteps;
                   nextSteps = new LinkedList<>();
                }
            }
            return -1;
        }
        
        public int findMinStep(String board, String hand) {
            return BFS(board, encode(hand));
        }
    }
    

Log in to reply
 

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