Connection Status:
Competition Arena > CmpdWords

CmpdWords

SRM 268 · 2005-10-18 · by dgoodman

SRM 268 · 2005-10-18 · by dgoodman · Brute Force, String Manipulation
Class Name: CmpdWords
Return Type: int
Method Name: ambiguous
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Some languages allow the use of compound words, words that are the concatenation of words from the language's dictionary.

We have defined a language that consists of a dictionary of distinct words. We want to know whether we should allow the use of compound words constructed by concatenating exactly two distinct dictionary words. The potential problem is that a compound word is ambiguous if either (or both) of the following conditions applies:

  1. the compound word is a dictionary word
  2. the compound word can be formed in more than one way.

For example, if "am","eat","a", "meat", "hook", and "meathook" were all in the dictionary, then "meathook" would be ambiguous according to the first condition, and "ameat" would be ambiguous according to the second condition.

Create a class CmpdWords that contains a method ambiguous that is given a String[] dictionary and that returns the number of ambiguous words that would result from allowing the compounding of distinct pairs of dictionary words. An ambiguous word should be counted only once, no matter how many different ways it could be formed.

Note that compound words are NOT added to the dictionary. So the dictionary {"a", "b","c"} does not allow "abc" as a compound word.

Constraints

  • dictionary will contain between 1 and 50 elements inclusive.
  • The elements of dictionary will be distinct.
  • Each element of dictionary will contain between 1 and 20 characters inclusive.
  • Each character in each element of dictionary will be a lowercase letter 'a'-'z'.
Examples
0)
{"am","eat","a", "meat", "hook","meathook"}
Returns: 2

"meathook" and "ameat" are ambiguous as explained above.

1)
{"a","b","c"}
Returns: 0

All the compound words are: "ab","ac","bc","ba","ca","cb" and none of these is ambiguous.

2)
{"a","aa","aaa"}
Returns: 3

The ambiguous words are "aaa": ("a"+"aa" and "aa"+"a" and "aaa") "aaaa": ("a"+"aaa" and "aaa"+"a") "aaaaa": ("aa"+"aaa" and "aaa"+"aa")

3)
{"abc","bca","bab","a"}
Returns: 1

"abc"+"a" = "a"+"bca"

4)
{"ab","ba","aa","aba","a","b"}
Returns: 10

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

Coding Area

Language: C++17 · define a public class CmpdWords with a public method int ambiguous(vector<string> dictionary) · 62 test cases · 2 s / 256 MB per case

Submitting as anonymous