Connection Status:
Competition Arena > WordTrain

WordTrain

SRM 247 · 2005-06-18 · by dgoodman

SRM 247 · 2005-06-18 · by dgoodman · Graph Theory, Sorting, String Manipulation
Class Name: WordTrain
Return Type: String
Method Name: hookUp
Arg Types: (vector<string>)
Problem Statement

Problem Statement

We have a collection of train cars. We want to hook them together to get the train with the most cars possible. Some cars have a unique front end, and some can have either end in front. Two cars can be coupled together only if their coupling mechanisms are compatible.

Each car is described by a String of uppercase letters. The front end is the end with the letter that comes first in the alphabet (if it starts and ends with the same letter, either end can be in front). Two words can be hooked together only if the two adjoining ends have the same letter. Create a class WordTrain that contains the method hookUp that takes cars, a String[], and returns a String which is the longest word train that can be made from cars.

If more than one train of the longest length is possible, return the one that comes first alphabetically. Remember that the length of a train is the number of cars, not the number of letters.

The returned string should be all the cars in the train, starting at the front of the train, concatenated with '-' showing the coupling between adjacent cars. For alphabetic breaking of ties, the '-' is included in its usual order in the ASCII sequence.

Constraints

  • cars contains between 1 and 50 elements inclusive.
  • Each element of cars contains only uppercase letters ('A'-'Z').
  • Each element of cars contains between 3 and 10 characters inclusive.
Examples
0)
{"CBA","DAA","CXX"}
Returns: "ABC-CXX"

This is the only possible train of length 2. Note that CBA needed to be reversed so that it was facing the right direction.

1)
{"ACBA"}
Returns: "ABCA"
2)
{"AUTOMATA","COMPUTER","ROBOT"}
Returns: "COMPUTER-ROBOT"
3)
{"AAA","AAAA","AAA","AAA"}
Returns: "AAA-AAA-AAA-AAAA"

'-' sorts before uppercase letters

4)
{"ABA","BBB","COP","COD","BAD"}
Returns: "BBB-BAD"

Submissions are judged against all 89 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WordTrain with a public method string hookUp(vector<string> cars) · 89 test cases · 2 s / 256 MB per case

Submitting as anonymous