⭐ 题目日期：

字节 - 25届秋招

🌳 题目描述：

给定一个字符串数组，例如 ["wasf", "fasd", "dsa", "asnsw"]，判断这个数组里面的元素能不能全部相连成环，即"asnsw"→"wasf"→"fasd"→"dsa"→"asnsw"。

🧗难度系数：

⭐️ ⭐️ ⭐ ️ ⭐ ⭐

📝思路分析：

这道题表面上考的是字符串，实际上需要转化为图论中的欧拉回路问题求解。将字符串的首字符和尾字符视为节点。每个字符串表示一条从首字符到尾字符的有向边 (如“dsa”可以转化成 d --> a)。欧拉回路有两个判定条件：

1. 连通性：图中的所有节点必须是连通的，即图的每个部分都是可达的。
2. 入读和出度：对于每个节点，入读必须等于出度。

如果上述条件满足，则存在欧拉回路，即可以将字符串连接成一个环。

💻代码：

Java

public boolean canFormCircle(String[] words) {
 if (words == null || words.length == 0) {
     return false;
 }

    int ALPHABET_SIZE = 26;
    int[] inDegrees = new int[ALPHABET_SIZE];
    int[] outDegrees = new int[ALPHABET_SIZE];
    List<List<Integer>> graph = new ArrayList<>();

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        graph.add(new ArrayList<>());
    }

    for (String word : words) {
        char startChar = word.charAt(0);
     char endChar = word.charAt(word.length() - 1);
        int startNode = startChar - 'a';
        int endNode = endChar - 'a';

        graph.get(startNode).add(endNode);
        outDegrees[startNode]++;
        inDegrees[endNode]++;
    }

    for (int i = 0; i < ALPHABET_SIZE; i++) {
     if (inDegrees[i] != outDegrees[i]) {
            return false;
        }
 }

    return isStronglyConnected(graph, words[0].charAt(0) - 'a', ALPHABET_SIZE, inDegrees, outDegrees);
}

private boolean isStronglyConnected(List<List<Integer>> graph, int startNode, int ALPHABET_SIZE,
                                    int[] inDegrees, int[] outDegrees) {
    boolean[] visited = new boolean[ALPHABET_SIZE];
    dfs(graph, startNode, visited);
 for (int i = 0; i < ALPHABET_SIZE; i++) {
        if ((inDegrees[i] > 0 || outDegrees[i] > 0) && !visited[i]) {
            return false;
        }
    }

 return true;
}

private void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;
 for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

🚵🏻复杂度分析：

时间复杂度：O(n), n 为字符数组的长度

空间复杂度：O(n)，存储所有的边