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

我认为你可以通过维持孩子和父母的关系来实现这一点

    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;