Accepted but quite slow solution, BFS, try all possible insertions


  • 0
    J

    Basically try every possible insertion position and character. If found a solution, returns.

        public int findMinStep(String board, String hand) {
        	int [] count = new int[5];
        	for (int i=0;i<board.length();i++){
        		if (board.charAt(i)=='R') count[0]++;
        		if (board.charAt(i)=='Y') count[1]++;
        		if (board.charAt(i)=='B') count[2]++;
        		if (board.charAt(i)=='G') count[3]++;
        		if (board.charAt(i)=='W') count[4]++;
        	}
        	for (int i=0;i<hand.length();i++){
        		if (hand.charAt(i)=='R'&&count[0]>0) count[0]++;
        		if (hand.charAt(i)=='Y'&&count[1]>0) count[1]++;
        		if (hand.charAt(i)=='B'&&count[2]>0) count[2]++;
        		if (hand.charAt(i)=='G'&&count[3]>0) count[3]++;
        		if (hand.charAt(i)=='W'&&count[4]>0) count[4]++;
        	}
        	for (int i=0;i<5;i++){
        		if (count[i]<3 && count[i]>0) return -1;
        	}
        	
        	HashMap<Character, Integer> handMap = new HashMap<Character, Integer>();
        	for (int i=0;i<hand.length();i++){
        		if (!handMap.containsKey(hand.charAt(i)))
        			handMap.put(hand.charAt(i), 0);
        		handMap.put(hand.charAt(i), handMap.get(hand.charAt(i))+1);
        	}
        	
            ArrayDeque<String> bq = new ArrayDeque<String>();
            ArrayDeque<HashMap<Character, Integer>> hq = new ArrayDeque<HashMap<Character, Integer>>();
            bq.add(board);
            hq.add(handMap);
            int step = 0;
            while(!bq.isEmpty()){
            	step++;
            	int l = bq.size();
            	for (int i=0;i<l;i++){
            		String b = bq.poll();
            		HashMap<Character, Integer> h = hq.poll();
            		for (int j=1;j<=b.length();j++){
            			
            			for (char k:h.keySet()){
            				String t = "";
            				if (j==b.length()&& j>1) continue;
            				if ((j==b.length() && j==1)|| k==b.charAt(j)||k==b.charAt(j-1))
            					t = ins(b, k, j);
        					else continue;
            				if (t=="") return step;
            				bq.add(t);
            				HashMap<Character, Integer> nmap = (HashMap<Character, Integer>) h.clone();
            				if (nmap.get(k)>1) nmap.put(k, nmap.get(k)-1);
            				else
            					nmap.remove(k);
            				hq.add(nmap);
            			}
            		}
            	}
            }
            return -1;
        }
    
        String ins (String b, char c, int p){
        	int l = p-1, r = p, cur = 1, np=p, l1=0,r1=0;
        	StringBuilder res = new StringBuilder(b);
        	while (l>-1 || r<b.length()){
        		while (l>-1 && b.charAt(l)==c){
        			l--;
        			cur++;
        		}
        		while (r<b.length() && b.charAt(r)==c){
        			r++;
        			cur++;
        		}
        		
        		if (cur<3){
        			res.delete(l1,r1);
        			res.insert(np, c);
        			return res.toString();
        		}
        		else{
        			if (l==-1 && r==b.length())
        				return "";
        			if (l>-1){
        				c = b.charAt(l);
        				l1 = l;
        				r1 = Math.min(r,b.length());
        				np = l;
        				cur = 1;
        				l--;
        				
        			}
        			else{
        				c= b.charAt(r);
        				l1 = Math.max(l, 0);
        				r1 = r+1;
        				r++;
        				np = l+1;
        				cur = 1;
        			}
        		}
        	}
        	return Character.toString(c);
        }
    

Log in to reply
 

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