MatchingPatterns | Topcoder Archive

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 String[] patterns.

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.

Definition

Class:: MatchingPatterns
Method:: solve
Parameters:: int, int[], String[]
Returns:: String
Method signature:: String solve(int N, int[] L, String[] patterns)
(be sure your method is public)

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.

Examples

```
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.

{1, 2, 3, 4}

{"ABCD", "DxAyzB"}

Returns: "yzzzxyyzzz"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.