祖玛游戏

/*
思路：
1. 使用Java Streams API简化操作，但本题使用Streams优势不大，主要体现在遍历和集合操作上。
2. 仍然是回溯法，尝试所有可能的插入方案。
3. 对于每一种方案，计算出插入后形成三个或以上相同颜色的球后，消除的结果。
4. 使用一个哈希表记录已经处理过的局面，避免重复计算。
*/
 
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
 
public class ZumaGameStream {
    public int findMinStep(String board, String hand) {
        Map<String, Integer> memo = new HashMap<>();
        int result = dfs(board, hand, memo);
        return result == Integer.MAX_VALUE ? -1 : result;
    }
 
    private int dfs(String board, String hand, Map<String, Integer> memo) {
        if (board.isEmpty()) return 0;
        if (hand.isEmpty()) return Integer.MAX_VALUE;
        String key = board + " " + hand;
        if (memo.containsKey(key)) return memo.get(key);
 
        int result = IntStream.range(0, hand.length())
                .mapToObj(i -> hand.charAt(i))
                .flatMap(c -> IntStream.rangeClosed(0, board.length())
                        .mapToObj(j -> insertAndEliminate(board, j, c, hand.substring(0, hand.indexOf(c)) + hand.substring(hand.indexOf(c) + 1))))
                .filter(newBoard -> newBoard != null)
                .map(newBoard -> dfs(newBoard, hand.replaceFirst(c + "", ""), memo) + 1)
                .min(Integer::compareTo)
                .orElse(Integer.MAX_VALUE);
 
        memo.put(key, result);
        return result;
    }
 
    private String insertAndEliminate(String board, int pos, char c, String newHand) {
        StringBuilder newBoard = new StringBuilder(board);
        newBoard.insert(pos, c);
        return eliminate(newBoard.toString());
    }
 
    private String eliminate(String board) {
        int i = 0;
        while (i < board.length()) {
            int j = i;
            while (j < board.length() && board.charAt(j) == board.charAt(i)) j++;
            if (j - i >= 3) {
                return eliminate(board.substring(0, i) + board.substring(j));
            } else {
                i = j;
            }
        }
        return board;
    }
}