SetOfPatterns
SRM 390 · 2008-02-02 · by srbga
SRM 390 · 2008-02-02 · by srbga · Advanced Math, Dynamic Programming, String Manipulation
Problem Statement
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.
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
0)
{"?"}
1
Returns: 26
Every lowercase letter matches this pattern.
1)
{"a","b","c"}
1
Returns: 3
"a" or "b" or "c".
2)
{"a?","?b"}
2
Returns: 1
The only possible solution is "ab".
3)
{"?????"}
1
Returns: 881343
26^5 mod 1000003 = 881343.
4)
{"?","?"}
1
Returns: 0
6)
{"a??","?a?","??a"}
2
Returns: 75
25*3=75.
Submissions are judged against all 124 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SetOfPatterns with a public method int howMany(vector<string> patterns, int k) · 124 test cases · 2 s / 256 MB per case