Java 18ms Solution


  • 0

    After reading https://discuss.leetcode.com/topic/75434/recursive-java-solution, I rewrote my TLE solution.
    The difference from my solution to ruben3's is I use StringBuffer to deal with boards and get a little bit improvement in the time cost. Anyway, the overall idea is the same. Thanks to ruben3 for the brilliant and clean solution!

    PS: Be aware of passing the StringBuffer as reference.

    public int findMinStep(String board, String hand) {
        Map<Character,Integer>handMap = new HashMap<>();
        handMap.put('R',0);
        handMap.put('Y',0);
        handMap.put('B',0);
        handMap.put('G',0);
        handMap.put('W',0);
        for(int i = 0;i<hand.length();i++){
            handMap.put(hand.charAt(i),handMap.get(hand.charAt(i)) + 1);
        }
        StringBuffer subBoard = new StringBuffer(board);
        return getRest(subBoard,handMap);
    }
    private  int getRest(StringBuffer subBoard, Map<Character,Integer> handMap){
        int min = Integer.MAX_VALUE;
        int len = subBoard.length();
        cleanBoard(subBoard);
        if(subBoard.length()==0) return 0;
        int i = 0;
        while(i<subBoard.length()){
            char start = subBoard.charAt(i);
            int j = i;
            while(j+1<subBoard.length()&&subBoard.charAt(j+1)==start){
                j++;
            }
            int need = 3 - (j-i+1);
            if(handMap.get(start)<need){
                i++;
                continue;
            }
            StringBuffer nextSb = new StringBuffer(subBoard);
            for(int k = 0;k<need;k++){
                nextSb.insert(j,start);
            }
            handMap.put(start,handMap.get(start)-need);
            int next = getRest(nextSb,handMap);
            if(next!=-1){
                min = need + next<min?need + next:min;
            }
            handMap.put(start,handMap.get(start)+need);
            i = j+1;
        }
        if(min==Integer.MAX_VALUE) min = -1;
        return min;
    }
    
    private  void cleanBoard(StringBuffer subBoard){
        if(subBoard.length()==0) return;
        int start = 0;
        int count = 0;
        char c = subBoard.charAt(start);
        int i = 0;
        boolean cleaned = false;
        while(i<subBoard.length()){
            if(subBoard.charAt(i)==c){
                count++;
                i++;
            }
            else{
                if(count>=3){
                    cleaned = true;
                    subBoard.delete(start,i);
                }
                start = i;
                count = 0;
                if(i>=subBoard.length()) break;
                c = subBoard.charAt(start);
            }
        }
        if(count>=3){
            cleaned = true;
            subBoard.delete(start,i);
        }
        if(cleaned){
            cleanBoard(subBoard);
        }
    }

  • 0
    J
    This post is deleted!

Log in to reply
 

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