wocagav's blog

Help in graph problem
By wocagav, history, 3 years ago, In English

There is an array of strings. Suppose there is a string whose last character matches with the first character of another string. In that case those two form a ring. You have the find the maximum length of the ring formed by the strings in the array. Let me explain the problem with an example. Suppose the array of strings is {ear, track, tired, rat, doe}. Here the maximum ring will be ear->rat->tired->doe>ear. So, the length will be 4.

If possible please provide code also .

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    in linear time.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I don't think it can be done in linear time, as essentially you are finding longest cycle in the graph, which has to be exponential according to me or maybe I am missing something.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What is the upper bound on the number of strings and the size of the alphabet? This cannot be done in linear time, but it may still be possible. This depends on the number of letters in the alphabet (i.e. is it only lowercase letters, or are uppercase letters allowed?) and on the maximum number of strings.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is the approach for O(n*n) solution.

First of all, to work with graphs , we have to map strings with some integer(let by index in this problem).

Make the adjacency list as follows:

for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
	if(i==j) continue;
	if(v[i][0] == v[j][(v[j].length()-1)] ) adj[i].push_back(j);
}

Now, by simply traversing in graph, find out the largest possible cycle.

→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Build a graph from the strings first. Then the size of the biggest strongly connected component is the answer. I haven't tried yet so I'm not sure whether it's correct or not.

→ Reply