java - 如何打印出BFS所走的路径？

Question

我正在解决 Leetcode 中的一个问题，其中我们给出了一个从起始组合 0000 开始的锁定组合。您一次只能旋转一个锁轮，并且必须使用尽可能少的圈数来完成此操作可能的。我有我的解决方案来做到这一点，并且它工作得很好，但我不知道如何实际打印出 BFS 达到该解决方案所需的路径(即用于达到它的中间组合)。任何帮助将不胜感激!

class Solution {

    private static final String START = "0000";

    public int openLock(String[] deadends, String target) {
        if (target == null || target.length() == 0) return -1;
        Set<String> visited = new HashSet<>(Arrays.asList(deadends));
        Queue<String> queue = new LinkedList<>();
        int level = 0;
        queue.offer(START);

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String currentLock = queue.poll();
                if (!visited.add(currentLock)) continue;
                if (currentLock.equals(target)) return level;

                for (String nextLock : getNextStates(currentLock)) {
                    if (!visited.contains(nextLock)) queue.offer(nextLock);
                }
            }
            level++;
        }

        return -1;
    }

    private List<String> getNextStates(String lock) {
        List<String> locks = new LinkedList<>();
        char[] arr = lock.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            arr[i] = c == '9' ? '0' : (char) (c + ((char) 1));
            locks.add(String.valueOf(arr));
            arr[i] = c == '0' ? '9' : (char) (c - ((char) 1));
            locks.add(String.valueOf(arr));
            arr[i] = c;
        }
        return locks;
    }
}

Answer 1

我认为你可以通过维持 child 与 parent 的关系来实现这一目标。

    Map<String,String> childToParent = new HashMap<String,String>();
    String currentLock = null;
    boolean found = false;
    while (!queue.isEmpty() && !found) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String currentLock = queue.poll();
            if (!visited.add(currentLock)) continue;
            if (currentLock.equals(target)){
                found = true;
                break;
            }
            for (String nextLock : getNextStates(currentLock)) {

                if (!visited.contains(nextLock)){
                   queue.offer(nextLock);
                   childToParent.put(nextLock,currentLock);
                  }
            }
        }
        level++;
    }
    if(!found){
     return -1;
    }
    // Printing path 
    int level = 0;
    while(childToParent.get(currentLock) != null){
        System.out.println(currentLock);
        currentLock = childToParent.get(currentLock);
        level++; 
    }
    System.out.println(currentLock);
    return level;