如何打印出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

我认为您可以通过维持孩子的父母关系来完成它。

Answer 2

就像@Tarun所说，您可以保持孩子与父母的关系。我有一种更好的方法，但是首先我要谈谈您还有什么其他问题。第一个是您正在执行此操作：您认为Set<String> visited = new HashSet<>(Arrays.asList(deadends)); Arrays.asList(...)应该包含String中的每个deadends。因此，您应该将其更改为：