Connection Status:
Competition Arena > Thesaurus

Thesaurus

SRM 215 · 2004-10-16 · by dgoodman

SRM 215 · 2004-10-16 · by dgoodman · Sorting, String Manipulation
Class Name: Thesaurus
Return Type: String[]
Method Name: edit
Arg Types: (vector<string>)
Problem Statement

Problem Statement

An entry in a Thesaurus is a list of words that are all synonyms. Each entry contains no duplicates within it. It is possible that two entries might have some common words, but the editors (who are somewhat cheap) have decided that if any two entries have 2 or more words in common then they should be combined into a single entry.

This editing process may produce new entries which can be combined. The final Thesaurus must contain no pair of entries that have 2 or more words in common. Of course, each entry must contain no duplicates.

Create a class Thesaurus that contains a method edit that is given a String[] entry, the entries in the original Thesaurus. The method returns the edited Thesaurus as a String[]. Each element of entry has no leading or trailing spaces and has its words separated by a single space. Each element of the return should also have no leading or trailing spaces and have its words separated by a single space. In addition, the words within each element of the return must be in alphabetical order, and the elements in the return must appear in alphabetical order.

Constraints

  • entry will contain between 1 and 50 elements inclusive.
  • Each element of entry will contain between 1 and 50 characters inclusive.
  • Each element of entry will consist of 1 or more "words" separated by single spaces.
  • Each element of entry will contain no leading or trailing spaces.
  • Each "word" will consist of 1 or more lowercase letters 'a'-'z'
  • No element of entry will contain two identical words.
Examples
0)
{"ape monkey wrench", "wrench twist strain"}
Returns: { "ape monkey wrench",  "strain twist wrench" }

These two entries have only one common word so they cannot be combined. After rearranging the words within each entry to put the words into alphabetical order, the first entry is first alphabetically.

1)
{"ape monkey wrench", "wrench twist strain", "monkey twist frugue"}
Returns: { "ape monkey wrench",  "frugue monkey twist",  "strain twist wrench" }

No entries could be combined, but two had to be arranged, and the order was changed.

2)
{"ape monkey wrench", "wrench twist strain", "monkey twist frugue strain"}
Returns: { "ape frugue monkey strain twist wrench" }

The first two entries could not be combined, but the last two could. After they were combined, the first entry shared both "wrench" and "monkey" with the new combined entry, so we ended up with just one entry.

3)
{"a"}
Returns: { "a" }
4)
{"c b a","a b c","c d","d e","e d b"}
Returns: { "a b c",  "b d e",  "c d" }

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

Coding Area

Language: C++17 · define a public class Thesaurus with a public method vector<string> edit(vector<string> entry) · 21 test cases · 2 s / 256 MB per case

Submitting as anonymous