PlayingCubes

TCO05 Sponsor 3 · 2005-08-16 · by Olexiy

TCO05 Sponsor 3 · 2005-08-16 · by Olexiy · Brute Force

Show categories

Class Name: PlayingCubes

Return Type: int[]

Method Name: composeWords

Arg Types: (vector<string>, vector<string>)

Problem Statement

Children are used to playing with special cubes with letters written on the cubes' faces. The goal of the game is to compose words using such cubes. If you want to compose the word "DOG", you must find 3 cubes, one containing the letter 'D', one containing the letter 'O', and one containing the letter 'G', and orient them so the proper letters are facing upward.

You are also given a String[] words, each element of which contains a word that you would like to spell out using the cubes. Return a int[] containing the 0-based indices of each of the words in words that can be composed using the given cubes. Indices in the return value must be sorted in ascending order.

Constraints

cubes will contain between 2 and 8 elements, inclusive.
Each element of cubes will contain exactly 6 uppercase letters ('A' - 'Z').
words will contain between 1 and 50 elements, inclusive.
Each element of words will contain between 2 and 8 uppercase letters ('A' - 'Z'), inclusive.

Examples

{"ABCDEF", "DEFGHI", "OPQRST", "ZZZZZZ", "YYYYYY"}
{"CAT", "DOG", "PIZZA"}
Returns: {1 }

We can form the word "DOG" using 'D' from the first cube, 'O' from the third and 'G' from the second. Note that if we had used the second cube to get 'D' instead, we would be missing a 'G'.

{"ABCDEF", "DEFGHI", "OPQRST", "MNZLSA", "QEIOGH", "IARJGS"}
{"DOG", "CAT", "MOUSE", "BIRD", "CHICKEN", "PIG", "ANIMAL"}
Returns: {0, 1, 3, 5 }

{"ABCDEF", "DEFGHI", "OPQRST", "ZZZZZZ", "YYYYYY"}
{"FOG", "DEFINE", "FORK", "YAHOO", "YAHO"}
Returns: {0, 4 }

{"AAAAAA", "AAAAAA", "AAAAAA", "AAAAAA"}
{"AA", "AAA", "AAAA", "AAAAA", "AAAAAA"}
Returns: {0, 1, 2 }

{"ABCDEF", "DEFGHI", "OPQRST", "ZZZZZZ", "ZZZZZZ"}
{"CAT", "DOG", "PIZZA"}
Returns: {1, 2 }

{"AAAAAA", "AAAAAA","AAAAAA", "AAAAAA","AAAAAA", "AAAAAA","AAAAAA", "AAAAAA"}
{"AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", 
 "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB", "AAAAAAAB"
}
Returns: { }

This is the biggest case I think. I am not sure if we should include it into examples.

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

Coding Area

Language: C++17 · define a public class PlayingCubes with a public method vector<int> composeWords(vector<string> cubes, vector<string> words) · 46 test cases · 2 s / 256 MB per case