Circle Of Strings

Given an array arr of lowercase strings, determine if the strings can be chained together to form a circle.
A string X can be chained together with another string Y if the last character of X is the same as the first character of Y. If every string of the array can be chained with exactly two strings of the array(one with the first character and the second with the last character of the string), it will form a circle.

For example, for the array arr[] = {“for”, “geek”, “rig”, “kaf”} the answer will be Yes as the given strings can be chained as “for”, “rig”, “geek” and “kaf”

Examples

Input: arr[] = ["abc", "bcd", "cdf"]
Output: 0
Explaination: These strings can't form a circle because no string has 'd'at the starting index.

Input: arr[] = ["ab" , "bc", "cd", "da"]
Output: 1
Explaination: These strings can form a circle of strings.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)

Constraints: 
1 ≤ length of strings ≤ 20

Approach 01:

class Solution {
public:
    void dfs(int currentNode, vector<bool>& visited, vector<vector<int>>& adjacencyList) {
        visited[currentNode] = true;
        
        for (int neighbor : adjacencyList[currentNode]) {
            if (!visited[neighbor])
                dfs(neighbor, visited, adjacencyList);
        }
    }

    int isCircle(vector<string>& words) {
        vector<int> inDegree(26, 0); // In-degree of each character
        vector<int> outDegree(26, 0); // Out-degree of each character
        vector<vector<int>> adjacencyList(26); // Adjacency list representation of the graph

        // Step 1: Create adjacency list
        // Step 2: Calculate in-degree and out-degree of nodes simultaneously
        for (const string& word : words) {
            int startCharIndex = word.front() - 'a';
            int endCharIndex = word.back() - 'a';
            
            adjacencyList[startCharIndex].push_back(endCharIndex);
            inDegree[endCharIndex]++;
            outDegree[startCharIndex]++;
        }

        // For an Eulerian Circuit to exist, in-degree and out-degree of each node should be the same
        for (int i = 0; i < 26; i++) {
            if (inDegree[i] != outDegree[i])
                return false;
        }

        // Graph Traversal
        vector<bool> visited(26, false);
        int startingNode = words[0][0] - 'a';
        dfs(startingNode, visited, adjacencyList);

        // Check if all nodes with non-zero in-degree are visited
        for (int i = 0; i < 26; i++) {
            if (inDegree[i] > 0 && !visited[i])
                return false;
        }

        return true;
    }
};

class Solution:
    def dfs(self, currentNode, visited, adjacencyList):
        visited[currentNode] = True
        
        for neighbor in adjacencyList[currentNode]:
            if not visited[neighbor]:
                self.dfs(neighbor, visited, adjacencyList)

    def isCircle(self, words):
        inDegree = [0] * 26  # In-degree of each character
        outDegree = [0] * 26  # Out-degree of each character
        adjacencyList = [[] for _ in range(26)]  # Adjacency list representation of the graph

        # Step 1: Create adjacency list
        # Step 2: Calculate in-degree and out-degree of nodes simultaneously
        for word in words:
            startCharIndex = ord(word[0]) - ord('a')
            endCharIndex = ord(word[-1]) - ord('a')
            
            adjacencyList[startCharIndex].append(endCharIndex)
            inDegree[endCharIndex] += 1
            outDegree[startCharIndex] += 1

        # For an Eulerian Circuit to exist, in-degree and out-degree of each node should be the same
        for i in range(26):
            if inDegree[i] != outDegree[i]:
                return 0

        # Graph Traversal
        visited = [False] * 26
        startingNode = ord(words[0][0]) - ord('a')
        self.dfs(startingNode, visited, adjacencyList)

        # Check if all nodes with non-zero in-degree are visited
        for i in range(26):
            if inDegree[i] > 0 and not visited[i]:
                return 0

        return 1

Time Complexity

• Building the Graph:

  Constructing the adjacency list and calculating the in-degrees and out-degrees of each node takes \(O(m)\), where m is the number of words in the input vector. Each word is processed once, and accessing characters or modifying vectors is an \(O(1)\) operation.

• DFS Traversal:

  The depth-first search (DFS) traversal over the graph has a time complexity of \(O(V + E)\), where V is the number of vertices (in this case, up to 26 representing lowercase English letters), and E is the number of edges (total number of characters processed from the words).

• Checking Degrees:

  Checking if the in-degree and out-degree of each node are equal takes \(O(26)\) since there are only 26 lowercase English letters.

• Overall Time Complexity:

  The overall time complexity of the solution is \(O(m + V + E) = O(m + E)\). Given that V is a constant (26 letters), the complexity is mainly determined by the number of words and the total number of characters in the words.

Space Complexity

• Adjacency List:

  The adjacency list representation of the graph takes \(O(V + E)\) space. Here, \(O(V)\) is the space for the vector of size 26, and \(O(E)\) is the space for the edges in the graph. Since V is constant (26), the space complexity is dominated by \(O(E)\).

• In-degree and Out-degree Arrays:

  Both inDegree and outDegree arrays have a fixed size of 26, resulting in a space complexity of \(O(1)\).

• Visited Array:

  The visited array also has a fixed size of 26, resulting in a space complexity of \(O(1)\).

• Recursive Call Stack for DFS:

  The space complexity of the recursive DFS calls is \(O(V) = O(26) = O(1)\) since the maximum depth of the recursion is limited by the number of vertices (26).

• Overall Space Complexity:

  The overall space complexity is \(O(E)\), where \(E\) is the total number of edges in the graph.