Connection Status:
Competition Arena > BuildString

BuildString

Rookie SRM 18 · 2022-10-10 · by erinn

Rookie SRM 18 · 2022-10-10 · by erinn · Dynamic Programming
Class Name: BuildString
Return Type: String
Method Name: isPossible
Arg Types: (vector<string>, string)
Problem Statement

Problem Statement

You are given a String[] parts. You are also given a String target. The goal will be to use some or all of the parts to concatenate together to build the target string. You may use the same part multiple times, and it is not necessary to use all of the parts.

Return "YES" if it is possible to build the target string, otherwise return "NO".

Constraints

  • parts will contain between 1 and 50 elements, inclusive.
  • Each element of parts will contain between 1 and 50 uppercase ('A'-'Z') characters, inclusive.
  • target will contain between 1 and 50 uppercase ('A'-'Z') characters, inclusive.
Examples
0)
{ "TOP", "CODER" }
"TOPCODER"
Returns: "YES"

It's trivial to concatenate the two strings together.

1)
{ "BOTTOM", "CODER" }
"TOPCODER"
Returns: "NO"

This time it won't work.

2)
{ "ISS", "M", "IPPI" }
"MISSISSIPPI"
Returns: "YES"

Notice that we use "ISS" more than once, and that we're not using the parts in order.

3)
{ "A", "B", "C", "D", "R" }
"ABBACADABRA"
Returns: "YES"
4)
{ "A", "B", "C" }
"ABCD"
Returns: "NO"

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

Coding Area

Language: C++17 · define a public class BuildString with a public method string isPossible(vector<string> parts, string target) · 9 test cases · 2 s / 256 MB per case

Submitting as anonymous