play on words

Some of the secret doors contain a very interesting word puzzle. The team of
archaeologists has to solve it to open that doors. Because there is no
other way to open the doors, the puzzle is very important for us.
There is a large number of magnetic plates on every door. Every plate has one
word written on it. The plates must be arranged into a sequence in such a way that
every word begins with the same letter as the previous
word ends. For example, the word acm’’ can be followed by the word
motorola’’. Your
task is to write a computer program that will read the list of words and
determine whether it is possible to arrange all of the plates in
a sequence (according to the given rule) and consequently to open the door.

It seems to me, that it’s not so difficult (more interesting could be number of such sequences).

You just need to check if s[c] (number of words starting with character c), is the same as e[c] (number of words ending with character c) and there could be 2 characters where this condition does not hold (first character in first word and last character in last word), or it holds for all characters:


ab bc cd

s['a'] = 1; // first where condition is not ok
s['b'] = e['b'] // contition holds
s['c'] = e['c'] // contition holds
e['d'] = 1 // second where condition doesn't hold

example 2:

ab ba // condition holds for all characters

ab ba cd dc ? // condition holds for all characters

1 Like