clean dfs java solution beat 100% so far, easy understand


  • 0
    N
    public int findMinStep(String board, String hand) {
        Map<Character, Integer> mp = new HashMap<>();
        for(int i = 0; i < hand.length(); i++){
            char c = hand.charAt(i);
            mp.put(c, mp.getOrDefault(c, 0) + 1);
        }
        return dfs(board, mp);
    }
    
    public int dfs(String board, Map<Character, Integer> mp){
        board = truncate(board);
        if(board.length() < 1) return 0;
        if(board.length() == 1 && mp.containsKey(board.charAt(0)) && mp.get(board.charAt(0)) >= 2) return 2;
        int min = Integer.MAX_VALUE;
        for(int i = 0, j = 1; j < board.length(); j++){
            char a = board.charAt(i);
            while(j < board.length() && a == board.charAt(j)) j++;
            if(mp.containsKey(a) && mp.get(a) >= 3 - (j - i)){
                int values = mp.get(a);
                int substract = 3 - (j - i);
                mp.put(a, values - substract);
                int number = dfs(board.substring(0, i) + board.substring(j), mp);
                i = j;
                if(number != -1) min = Math.min(min, substract + number);
                mp.put(a, values);
            }
            i = j;
        }
        return min == Integer.MAX_VALUE ? -1 : min;
    }
    
    public String truncate(String board){
        for(int i = 0, j = 1; j < board.length(); j++){
            while(j < board.length() && board.charAt(j) == board.charAt(i)){
                j++;
            }
            if(j - i >= 3) board = truncate(board.substring(0, i)  + board.substring(j));
            i = j;
        }
        return board;
    }

Log in to reply
 

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