CODEWITHSUNDEEP
c++sortingvectorstl-algorithm
mu_sa
mu_sa

Reputation: 2725

String vector sorting

I havent used sorting and alogorithms much and am Ok with vectors. Recently i faced an interesting question and want your suggestions with how to solve it. So, below is my question.

Q, I have been given 4 character strings in a vector and have to arrange those in a particular order depending on what those characters are. So, that the last character of any string should match with the first character of any other string and the last character of this string should be matched with the first character of any other string and this way i have to create a longest possible string.

For eg if i have a string vector like "ABCD" "TGHI" "DADC" "IYUR" "CXYT" so it would be arrange like "ABCD"then there would be the third string"DADC" then there would be the fifth string"CXYT" and so on So, the result will be "ABCD""DADC""CXYT""TGHI""IYUR".

Now,i was wondering if it would be a good idea to check each string with other string if it is 'compatible' according to the above rules.. so if i have 5 strings in the vector then i would have 5+4+3+2+1 possiblties and if for eg i have 20 strings then it would increase alot, so is this a good idea or is there any other good efficient solution to this... Thanks alot and hope (most of) you understand.

Upvotes: 0

Views: 231

Answers (2)

RussS
RussS

Reputation: 16576

Imagine every letter as a node in a graph. Each word represents a directed pathway between two letters in. "ACCA" defines A->A "BAAC" B-->C . Within this graph you would like to find a Eulerian Path. http://en.wikipedia.org/wiki/Eulerian_path . The Eulerian Path is defined as a path that visits every edge exactly once and since each edge represents a word that means you have used all the words!

Upvotes: 1

Sufian Latif
Sufian Latif

Reputation: 13356

A better approach may be to build a directed graph using the strings. There will be an edge from string s1 to string s2 if the last character of s1 is the same as the first character of s2. Then you can try to find the longest path in the graph.

Upvotes: 0

Related Questions