Simple Java Solution using BFS


  • 0
    H
    public class Solution {
    public int findMinStep(String board, String hand) {
        HashMap<Character, Integer> handMap = new HashMap<>();
        
        for(int i=0;i<hand.length();i++) {
            if(handMap.get(hand.charAt(i)) == null) {
                handMap.put(hand.charAt(i), 0);
            }
            handMap.put(hand.charAt(i), handMap.get(hand.charAt(i)) + 1);
        }
        
        Queue<String> queue = new LinkedList<>();
        Queue<Integer> levels = new LinkedList<>();
        HashMap<String, HashMap<Character, Integer>> map =  new HashMap<>();
        
        map.put(board, handMap);
        queue.add(board);
        levels.add(0);
        
        HashSet<String> visited = new HashSet<>();
        visited.add(board);
        while(!queue.isEmpty()) {
            String top = queue.poll();
            Integer level = levels.poll();
            
            if(top.equals("")) {
                return level;
            }
            
            List<String> candidates = getCandidates(top, map.get(top), map, visited);
            
            for(String ca :  candidates) {
                queue.offer(ca);
                levels.offer(level + 1);
            }
        }
        
        return -1;
    }
    
    public List<String> getCandidates(String str, HashMap<Character, Integer> handMap, HashMap<String, HashMap<Character, Integer>> map, HashSet<String> visited) {
        List<String> candidates = new ArrayList<>();
        for(Character c : handMap.keySet()) {
            for(int i=0;i<str.length();i++) {
                if(str.charAt(i) == c) {
                    String cand = refine(str.substring(0, i) + String.valueOf(c) + str.substring(i, str.length()));
                    if(!visited.contains(cand)) {
                        candidates.add(cand);
                        HashMap<Character, Integer> temp = new HashMap<>(handMap);
                        temp.put(c, temp.get(c) - 1);
                        if(temp.get(c) == 0) {
                            temp.remove(c);
                        }
                    
                        map.put(cand, temp);
                        visited.add(cand);
                    }
                }
            }
        }
        
        return candidates;
    }
    
    public String refine(String str) {
        String temp = "";
        while(true) {
            temp = str.replaceAll("([A-Z])(\\1{2,})", "");
            if(temp.length() == str.length())
                return temp;
            else
                str = temp;
        }
    }
    

    }


Log in to reply
 

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