SetOfPatterns | Topcoder Archive

Problem Statement

You are given a String[] patterns, each element of which is a single pattern. Each pattern contains only lowercase letters and question marks ('?'). A string matches a pattern if it has the same length as the pattern, and at each position, either the corresponding characters are equal or the character in the pattern is a question mark. For example, "abc" matches "a?c", but not "a?b" or "abc?". Return the number of strings consisting of only lowercase letters that match exactly k of the given patterns, modulo 1,000,003.

Definition

Class:: SetOfPatterns
Method:: howMany
Parameters:: String[], int
Returns:: int
Method signature:: int howMany(String[] patterns, int k)
(be sure your method is public)

Constraints

patterns will contain between 1 and 15 elements, inclusive.
k will be between 1 and the number of elements in patterns, inclusive.
Each element of patterns will contain between 1 and 50 characters, inclusive.
Each element of patterns will have the same length.
Each element of patterns will contain only lowercase letters ('a' - 'z') and question marks ('?').

Examples

```
{"?"}
```
```
1
```
```
Returns: 26
```
Every lowercase letter matches this pattern.
```
{"a","b","c"}
```
```
1
```
```
Returns: 3
```
"a" or "b" or "c".
```
{"a?","?b"}
```
```
2
```
```
Returns: 1
```
The only possible solution is "ab".
```
{"?????"}
```
```
1
```
```
Returns: 881343
```
26^5 mod 1000003 = 881343.

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.