Java DFS Iteration code, using Stack


  • 1
    L
    public int findMinStep(String board, String hand) {
            Map<Character, Integer> rootMap = new HashMap<>();
            for (char c : hand.toCharArray()) {
                if (!rootMap.containsKey(c)) {
                    rootMap.put(c, 1);
                } else {
                    rootMap.put(c, rootMap.get(c) + 1);
                }
            }
            int rootBall = hand.length();
            StringBuilder rootString = new StringBuilder(board);
            Stack<TreeNode> stack = new Stack<>();
            stack.push(new TreeNode(rootString, rootMap, rootBall));
            int result = Integer.MAX_VALUE;
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                // Leaf Node:
                if (node._cur.length() == 0) {
                    result = Math.min(hand.length() - node._remainBall, result);
                }
                // push children
                if (hand.length() - node._remainBall < result) {  // Improving performance by pruning
                    int i = 0; // start point
                    for (int j = 1; j <= node._cur.length(); j++) {
                        StringBuilder childcur = new StringBuilder(node._cur);
                        if (j == node._cur.length() || node._cur.charAt(j) != node._cur.charAt(i)) {
                            if (j - i >= 3) {
                                childcur.delete(i, j);
                                stack.push(new TreeNode(childcur, node._map, node._remainBall));
                            } else if (j - i < 3 && node._map.containsKey(node._cur.charAt(i)) && node._map.get(node._cur.charAt(i)) >= 3 - (j - i)) {
                                childcur.delete(i, j);
                                Map<Character, Integer> childMap = new HashMap<>(node._map);
                                childMap.put(node._cur.charAt(i), childMap.get(node._cur.charAt(i)) - (3 - (j - i)));
                                stack.push(new TreeNode(childcur, childMap, node._remainBall - (3 - (j - i))));
                            }
                            i = j; // set start point to cur position
                        }
                    }
                }
            }
            return result == Integer.MAX_VALUE ? -1 : result;
        }
    
        private class TreeNode {
            StringBuilder _cur;
            Map<Character, Integer> _map;
            int _remainBall;
            TreeNode(StringBuilder cur, Map<Character, Integer> map, int remainBall) {
                _cur = cur;
                _map = map;
                _remainBall = remainBall;
            }
        }
    

Log in to reply
 

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