DFS solution


  • 0
    public class Solution {
        public int findMinStep(String board, String hand) {
            int len=board.length();
            if(len==0) return 0;
            if(hand.length()==0) return -1;
            int res=Integer.MAX_VALUE;
            int i=0;
            while(i<len){
                char ati=board.charAt(i);
                int ballIndex=hand.indexOf(ati);
                if(ballIndex>=0){
                    int l=i-1, r=i+1;
                    while(l>=0&&board.charAt(l)==ati) l--;
                    while(r<len&&board.charAt(r)==ati) r++;
                    String newboard=null;
                    if(r-l==2) newboard=board.substring(0,l+1)+ati+ati+board.substring(r);
                    else{
                        newboard=board.substring(0,l+1)+board.substring(r);
                        newboard=check(newboard);
                    }
                    int tmp=
                    findMinStep(newboard,hand.substring(0, ballIndex)+hand.substring(ballIndex+1));
                    if(tmp>=0) res=Math.min(res,1+tmp);
                }
                i++;
                while(i<len&&board.charAt(i)==board.charAt(i-1)) i++;
            }
            return res==Integer.MAX_VALUE?-1:res;
        }
        
        public String check(String board){
            LinkedList<Character> stack=new LinkedList<>();
            StringBuilder res=new StringBuilder();
            int len=board.length();
            for(char x:board.toCharArray()){
                if(!stack.isEmpty()&&stack.peek()!=x){
                    int count=1;
                    char ty=stack.pop();
                    while(!stack.isEmpty()&&stack.peek()==ty){
                        count++;
                        stack.pop();
                    }
                    if(count<3) {
                        for(int c=0;c<count;c++) stack.push(ty);
                    }
                }
                stack.push(x);
            }
            if(!stack.isEmpty()){
                int count=1;
                char ty=stack.pop();
                while(!stack.isEmpty()&&stack.peek()==ty){
                    count++;
                    stack.pop();
                }
                StringBuilder tmp=new StringBuilder();
                if(count<3){
                    for(int c=0;c<count;c++) tmp.append(ty);
                }
                while(!stack.isEmpty()) tmp.append(stack.pop());
                res.append(tmp.reverse().toString());
            }
            return res.toString();
        }
    }
    

Log in to reply
 

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