Circle of strings

Intuition

Check if strings can be chained in a circle (each string starts with last char of previous). Eulerian circuit in directed graph.

Algorithm

1Build directed graph: edge from first char to last char of each string.
2Check: (1) all nodes with non-zero degree are connected (ignore zero-degree), (2) in-degree == out-degree for all nodes.

Common Pitfalls

•Eulerian circuit exists iff graph is connected (among used nodes) and all in-degrees equal out-degrees.

Circle of strings.java

Java

// Approach: Model as directed graph: each string adds edge from first to last character.
// Eulerian circuit exists iff the graph is connected and every node has equal in/out degree.
// Time: O(n * len) Space: O(26)
import java.util.*;

class Solution {
    public int isCircle(String arr[]) {
        int n = arr.length;

        if (n == 0)
            return 0;

        int[] inDegree = new int[26];
        int[] outDegree = new int[26];

        ArrayList<Integer>[] adj = new ArrayList[26];

        for (int i = 0; i < 26; i++)
            adj[i] = new ArrayList<>();

        for (String str : arr) {
            int first = str.charAt(0) - 'a';
            int last = str.charAt(str.length() - 1) - 'a';

            outDegree[first]++;
            inDegree[last]++;

            adj[first].add(last);
        }

        for (int i = 0; i < 26; i++) {
            if (inDegree[i] != outDegree[i])
                return 0;
        }

        int start = -1;
        for (int i = 0; i < 26; i++) {
            if (outDegree[i] > 0) {
                start = i;
                break;
            }
        }

        boolean[] visited = new boolean[26];
        dfs(start, adj, visited);

        for (int i = 0; i < 26; i++) {
            if (outDegree[i] > 0 && !visited[i])
                return 0;
        }

        return 1;
    }

    private void dfs(int node, ArrayList<Integer>[] adj, boolean[] visited) {
        visited[node] = true;

        for (int adjNode : adj[node]) {
            if (!visited[adjNode])
                dfs(adjNode, adj, visited);
        }
    }
}

Was this solution helpful?