TopCoder problem "SetOfPatterns" used in SRM 390 (Division II Level Three)



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

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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8307

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11124&pm=8307

Writer:

srbga

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Advanced Math, Dynamic Programming, String Manipulation