MatchingPatterns
SRM 834 · 2022-07-25 · by misof
Problem Statement
There are N variables, numbered from 0 to N-1. These variables are also labeled using the first N uppercase English letters ('A', 'B', 'C', ...).
Each variable represents a string of lowercase English letters ('a'-'z'). Additionally, each variable has a known fixed length: variable i represents a string of length L[i].
A word is a string of lowercase letters.
A pattern is a string that contains variables and lowercase letters.
An assignment is a sequence of N words that represent the values of our variables. (For each i, word i in this sequence must have length L[i].)
Given an assignment, the evaluation of a pattern is the word obtained by replacing each occurrence of each variable by its assigned value.
You are given N, L and the
Determine whether there is an assignment such that all the given patterns evaluate to the same word W. If yes, return any word W that can be obtained this way. If no, return an empty string.
Constraints
- N will be between 1 and 26, inclusive.
- L will have exactly N elements.
- Each element of L will be between 1 and 10, inclusive.
- patterns will have between 1 and 5 elements, inclusive.
- Each element of patterns will have between 1 and 50 characters, inclusive.
- Each character in patterns will be either a lowercase English letter ('a'-'z') or one of the first N uppercase English letters.
1
{2}
{"AAA"}
Returns: "hehehe"
The valid answers are precisely all strings of the form "xyxyxy" where x and y are any two (not necessarily distinct) lowercase letters.
2
{2, 3}
{"ABxA", "BxxB"}
Returns: "xxxxxxxx"
The returned string is the only correct return value for this test case.
3
{2, 3, 2}
{"ABxA", "yCCB"}
Returns: ""
There is no assignment for which these two patterns evaluate to the same word.
3
{4, 5, 6}
{"A", "B", "C"}
Returns: ""
These three patterns will never evaluate to words of the same length, so they clearly cannot evaluate to the same word.
4
{1, 2, 3, 4}
{"ABCD", "DxAyzB"}
Returns: "yzzzxyyzzz"
Submissions are judged against all 222 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MatchingPatterns with a public method string solve(int N, vector<int> L, vector<string> patterns) · 222 test cases · 2 s / 256 MB per case