java solution and thinking process


  • 0

    My idea is using brut force because the board is no longer than 20 and hand is no longer than 5. Every time we have using an element in hand, we will get a new board and a new hand, we can treat these two string as the same ting as the previous step. So a recursive solution come into my mind

    hope it helps~

    public class Solution {
        public int findMinStep(String board, String hand) {
            if(board == null || board.length() == 0) return 0;
            if(hand == null || hand.length() == 0) return -1;
            return helper(board , hand);
        }
        
        protected int helper(String board , String hand) {
            if(board == null || board.length() == 0) return 0;
            if(board.length() != 0 && hand.length() == 0) return -1;
            int res = Integer.MAX_VALUE;
            HashMap<Character,Integer> map = new HashMap<Character,Integer>();
            for(int i = 0 ; i < hand.length() ; i++) {
                char c = hand.charAt(i);
                map.put(c , map.getOrDefault(c , 0) + 1);
            }
            int left = 0;
            int right = 0;
            while(right < board.length()) {
                while(right < board.length() && board.charAt(right) == board.charAt(left)) {
                    right++;
                }
                int sub = right - left;
                char r = board.charAt(left);
                if(!map.containsKey(r)) {
                    left = right;
                    continue;
                }
                String t = board.substring(0 , right) + r + board.substring(right);
                String newboard = getnewboard(t);
                String newhand = getnewhand(hand , r);
                int num = helper(newboard , newhand);
                if(num >= 0) res = Math.min(res , 1 + helper(newboard , newhand));
                left = right;
            }
            return res == Integer.MAX_VALUE ? -1 : res;
        }
        
        protected String getnewboard(String s) {
            if(s.length() < 3) return s;
            int left = 0;
            int right = 0;
            while(right < s.length()) {
                while(right < s.length() && s.charAt(right) == s.charAt(left)) {
                    right++;
                }
                int sub = right - left;
                if(sub >= 3) {
                    return getnewboard(s.substring(0,left) + s.substring(right));
                }
                left = right;
            }
            return s;
        }
        
        protected String getnewhand(String hand , char r) {
            if(hand == null || hand.length() == 0) {
                return "";
            }
            for(int i = 0 ; i < hand.length() ; i++) {
                if(hand.charAt(i) == r) {
                    return hand.substring(0 , i) + hand.substring(i+1);
                }
            }
            return "";
        }
    }

Log in to reply
 

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