JAVA BFS Solution with Comments - Preprocess stickers


  • 0
    S

    This is just a working BFS solution....

    1. If sticker A does not have any character shows in target, we should ignore it.
    2. If number of useful characters in sticker A is all larger than number of useful characters in sticker B, we should never use sticker B.

    I preprocessed and do BFS with those meaningful stickers.

    class Solution {
        public int minStickers(String[] stickers, String target) {
            int[] t = new int[27];
            //bit 26 to record remaining character
            t[26] = target.length();
            Set<Character> set = new HashSet<>();
            Set<Character> checkSet = new HashSet<>();
            for(int i = 0; i < target.length(); i++) {
                t[target.charAt(i) - 'a']++;
                set.add(target.charAt(i));
                checkSet.add(target.charAt(i));
            }
            //mark valid stickers
            boolean[] valid = new boolean[stickers.length];
            int[][] stable = new int[stickers.length][26];
            for(int i = 0; i < stickers.length; i++) {
                for(int j = 0; j < stickers[i].length(); j++) {
                    char c = stickers[i].charAt(j);
                    if(set.contains(c)) {
                        stable[i][c - 'a']++;
                        valid[i] = true;
                        checkSet.remove(c);
                    }
                }
            }
            if(checkSet.size() > 0) return -1;
            // if sticker A include sticker B, remove sticker B
            for(int i = 0; i < stable.length; i++) {
                for(int j = i + 1; j < stable.length; j++) {
                    if(!valid[i] || !valid[j] || i == j) continue;
                    int judge = isIncluding(stable[i], stable[j]);
                    if(judge == 1) valid[j] = false;
                    else if(judge == -1) valid[i] = false;
                }
            }
            //BFS
            Deque<int[]> queue = new LinkedList<>();
            queue.add(t);
            int level = 1;
            while(true) {
                int size = queue.size();
                while(size-- > 0) {
                    int[] currState = queue.poll();  
                    for(int i = 0; i < stickers.length; i++) {
                        if(valid[i]) {
                            int[] nextState = new int[27];
                            boolean finished = true;
                            for(int j = 0; j < 26; j++) {
                                nextState[j] = currState[j] - stable[i][j];
                                if(nextState[j] > 0) finished = false;
                                nextState[26] += nextState[j] > 0 ? nextState[j] : 0;
                            }
                            if(finished) return level;
                            //if nothing change by using current sticker, don't put it back to queue.
                            if(nextState[26] < currState[26]) {
                                queue.offer(nextState);
                            }
                        }
                    }
                }
                level++;
            }
        }
        
        private int isIncluding(int[] a, int[] b) {
            boolean larger = true, smaller = true;
            for(int i = 0; i < 26; i++) {
                if(a[i] >= b[i]) smaller = false;
                else larger = false;
            }
            return larger ? 1 : smaller ? -1 : 0;
        }
    }

Log in to reply
 

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