华为OD机试 - 两个字符串间的最短路径问题（Java & JS & Python & C & C++）

题目描述：

给定一个字符串图（其中每个字符代表一个节点，并且所有节点都连接到其他节点）和两个节点A和B，请找出A和B之间的最短路径。

解决方案：

这个问题可以通过广度优先搜索（BFS）算法来解决。我们从节点A开始，并且我们在每一步扩展所有相邻节点。我们将记录每个节点的父节点，以便在找到最短路径时回溯。

以下是使用不同编程语言实现的解决方案：

1. Java:

public class ShortestPathBetweenTwoStrings {
    public String[] findShortestPath(String graph, String A, String B) {
        // 使用HashSet存储访问过的节点
        HashSet<Character> visited = new HashSet<>();
        // 使用LinkedList作为队列
        Queue<Pair> queue = new LinkedList<>();
        // 使用HashMap记录每个节点的父节点
        HashMap<Character, Character> parentMap = new HashMap<>();
 
        // 将起点加入队列
        queue.offer(new Pair(A.charAt(0), null));
        visited.add(A.charAt(0));
 
        // BFS搜索
        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            char currentChar = current.node;
            char parent = current.parent;
 
            // 如果当前节点是B，则找到了最短路径
            if (currentChar == B.charAt(0)) {
                // 从B回溯到A构建最短路径
                Stack<Character> stack = new Stack<>();
                while (parent != null) {
                    stack.push(currentChar);
                    currentChar = parent;
                    parent = parentMap.get(currentChar);
                }
                stack.push(currentChar); // 加入起点A
                String[] path = new String[stack.size()];
                for (int i = 0; i < path.length; i++) {
                    path[i] = String.valueOf(stack.pop());
                }
                return path;
            }
 
            // 扩展所有未访问的邻居节点
            for (int i = 0; i < graph.length(); i++) {
                if (graph.charAt(i) == currentChar && !visited.contains(graph.charAt(i))) {
                    visited.add(graph.charAt(i));
                    queue.offer(new Pair(graph.charAt(i), currentChar));
                    parentMap.put(graph.charAt(i), currentChar);
                }
            }
        }
        return new String[]{""}; // 如果没有找到路径，返回空数组或相应的错误信息
    }
 
    static class Pair {
        char node;
        Character parent;
 
        public Pair(char node, Character parent) {
            this.node = node;
            this.parent = parent;
        }
    }
}

2. JavaScript:

function findShortestPath(graph, A, B) {
    let visited = new Set();
    let queue = [];
    let parentMap = new Map();
 
    queue.push({ node: A, parent: null });
    visited.