Circle of strings Python (Interview Problem)

Question

Given an array of lowercase strings A[] of size N, 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 same as first character of Y. If every string of the array can be chained, it will form a circle.

For eg 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"

Example 1:

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

Example 2:

Input:
N = 4
A[] = { "ab" , "bc", "cd", "da" }
Output:
1
Explaination:
These strings can form a circle 
of strings.

My working correct code:

class Solution:
    def isCircle(self, N, A):
        
        visited = set()
        item1 = A[0]
        curr = item1[-1]
        visited.add(item1)
        
        for _ in range(len(A)):
            for item in A:
                if item not in visited and item[0] == curr:
                    visited.add(item)
                    curr = item[-1]
            # return visited
        if len(visited) == len(A):
            return 1
        else:
            return 0

Current Time Complexity:

O(n2)

Expected Time Complexity:

O(n)

How to make this more efficient and do the same work in a lot lesser time?

This is the classical problem of finding a cycle in a directed graph. This may help you finding references / other posts on SO. — Damien
– Damien, Commented Feb 23, 2021 at 11:26
The problem is with the time complexity, the question seems straight forward. — Shubham Prashar
– Shubham Prashar, Commented Feb 23, 2021 at 11:51
is it assured that the word cannot end with the letter it starts with? — Rustam Garayev
– Rustam Garayev, Commented Feb 23, 2021 at 12:13

Shamis · Accepted Answer · 2021-02-23 12:49:12Z

Constructing the graph:

Node for every letter.
Directed edge (u, v) for each word, u is the first letter of the word, v is the last letter.

And that's it, this is enough. A path in this graph represents a chain of words. (If we need to reconstruct it, we can save the words alongside the edges. It won't affect the complexity.
The construction of this graph costs us O(n) since it has 26 vertices and n edges.

Checking that the graph is strongly connected

Observation: if the graph isn't strongly connected, there can't exist a cycle over all its edges. This check can be done in a time O(V + E) by Tarjan's algorithm. Since the number of edges corresponds to the number of words we have, this is O(n) for our purpose. (Or most likely much faster since we have only 26 vertices if we take the a-z alphabet)

Finding the Euler cycle:

Observation: As we mentioned a path in this graph is a chain of words. We are looking for a cycle that would traverse all the edges. This is a well researched problem of finding an Euler cycle.

Since the graph is strongly connected, the Euler cycle exists as long as all degrees in the graph are even. Checking these edges can be done in a time linear with the number of vertices, so it does nothing to the complexity since there are only 26 of them . If we were to go and find the circular chain, the things would be a bit more difficult - however it can be done in O(E) by for example Hierholzer's algorithm.
Since the question was only a yes/no decision, finding the cycle shouldn't be necessary.

Note: Since there was the comment about words that start and end with the same letter: these won't change the result since every one of them adds one single-node loop to the graph, increasing its degree by 2.

Wow, this would work like a charm. The clever graph construction logic would drastically make the question simple and reduce complexity. Thanks for saving my day!

Shubham Prashar · Accepted Answer · 2021-02-23 19:05:51Z

Implementing Shamis's idea! Ran in 0.09s

from collections import defaultdict

class Solution:
    def __init__(self):
        self.vertList = defaultdict(list)

    def addEdges(self,u,v):
        self.vertList[u].append(v)
        
    # <- function to generate reversed graph ->
    def reverseTheGraph(self):
        g1 = Solution()
        for v in self.vertList:
            for nbr in self.vertList[v]:
                g1.addEdges(nbr,v) # reverse graph means the edges are reversed
        return g1
    
    # <- function for normal DFS traversal ->
    def DFS(self,v1,visited2,ans):
        visited2.add(v1)
        

        for nbr in self.vertList[v1]:
            if nbr not in visited2:
                self.DFS(nbr,visited2,ans)
    
    # <- function for finished time DFS traversal ->
    def finishedTimeDFS(self,givenVertex,visited1,stack):
        visited1.add(givenVertex)
        for nbr in self.vertList[givenVertex]:
            if nbr not in visited1:
                self.finishedTimeDFS(nbr,visited1,stack)
        stack.append(givenVertex)

    # <- function to check cycle using DFS ->
    def cycleCheckDFS(self,givenV,visited,currStack,vertList):
        visited.add(givenV)
        currStack.append(givenV)
        
        for nbr in vertList[givenV]:   
        # nbr = vertList[givenV]
            if nbr in currStack:
                return True
            else:
                if nbr not in visited:
                    cycleMila = self.cycleCheckDFS(nbr,visited,currStack,vertList)
                    if cycleMila is True:
                        return True
            currStack.pop()
        return False
    # <- the function called by the driver ->
    def isCircle(self, N, A):
        for item in A:
            first = item[0]
            last = item[-1]
            self.addEdges(first,last)
        r1 = A[0]
        givenV = r1[-1]
        stack = []
        visited1 = set()
        list1 = [ v for v in self.vertList]
        for vertices in list1:
            if vertices not in visited1:
                self.finishedTimeDFS(vertices,visited1,stack)
        reversedGraph = self.reverseTheGraph()
        visited2 = set()
        ans = []
        count = 0
        while len(stack)>0:
            curr = stack.pop()
            if curr not in visited2:
                reversedGraph.DFS(curr,visited2,ans)
                count += 1
                
            
       
        if count == 1:

        
        # <- CHECK FOR CONNECTED COMPONENT HERE ->
            r1 = A[0]
            givenV = r1[-1]
            visited3 = set()
            currStack = []
            
            result = self.cycleCheckDFS(givenV,visited3,currStack,self.vertList)
            if result == True:
                return 1
            else:
                return 0
        
        else:
            return 0

Link to the online judge -> LINK

Collectives™ on Stack Overflow

Circle of strings Python (Interview Problem)

2 Answers 2

Constructing the graph:

Checking that the graph is strongly connected

Finding the Euler cycle:

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Constructing the graph:

Checking that the graph is strongly connected

Finding the Euler cycle:

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related