Search and memorize Java solution


  • 2
    P

    Just searching and memorizing...
    It is not a good interview question because many codes are not related to the algorithm.

    public class Solution {
    	    public int findMinStep(String board, String hand) {
    	        HashMap<Character, int[]> mhand = new HashMap<Character, int[]>();
    	        mhand.put('R', new int[]{0});
    	        mhand.put('Y', new int[]{0});
    	        mhand.put('B', new int[]{0});
    	        mhand.put('G', new int[]{0});
    	        mhand.put('W', new int[]{0});
    	        for(char c:hand.toCharArray()){
    	                mhand.get(c)[0]++;
    	        }
    	        HashMap<String, Integer> record = new HashMap<String, Integer>();
    	        int min = helper(board, mhand, record);
    	        if(min>=10000){
    	            return -1;
    	        } else {
    	            return min;
    	        }
    	    }
    	    
    	    int helper(String board, HashMap<Character, int[]> hand, HashMap<String, Integer> record){
    	        if(board.length()==0){
    	            return 0;
    	        } else {
    	            int min = 10000;
                    for(int i=0;i<board.length();i++){
                        if(hand.get(board.charAt(i))[0]>0){
                            hand.get(board.charAt(i))[0]--;
                            String newboard = board.substring(0,i)+board.charAt(i)+board.substring(i);
                            newboard = further(newboard);
                            String c = code(newboard, hand);
    	                    if(record.containsKey(c)){
    	                    	min = Math.min(min, 1+record.get(c));
    	                    } else {
    	                    	int s = helper(newboard, hand, record);
    	                    	min = Math.min(min, 1+s);
    	                    	record.put(c, s);
    	                    }
                            hand.get(board.charAt(i))[0]++;
                        }
                    }
    	            return min;
    	        }
    	    }
    	    String further(String board){
    	        if(board.length()==0){
    	            return "";
    	        }
    	        int count=1;
    	        for(int i=1;i<board.length();i++){
    	            if(board.charAt(i-1)==board.charAt(i)){
    	                count++;
    	            } else {
    	                if(count>=3){
    	                    return further(board.substring(0, i-count)+board.substring(i));
    	                } else {
    	                    count=1;
    	                }
    	            }
    	        }
    	        if(count>=3){
    	            return board.substring(0, board.length()-count);
    	        }
    	        return board;
    	    }    
    	    String code(String board, HashMap<Character, int[]> hand){
    	    	StringBuilder sb = new StringBuilder();
    	    	sb.append(board);
    	    	for(Map.Entry<Character, int[]> e: hand.entrySet()){
    	    		sb.append(e.getKey());
    	    		sb.append(e.getValue()[0]);
    	    	}
    	    	return sb.toString();
    	    }
    }
    

Log in to reply
 

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