TopCoder problem "DigitMask" used in Delta Round 1 (Division I Level Two)



Problem Statement

    You will be given a list of patterns. Each pattern will contain only digits ('0'-'9'), question marks ('?'), and may potentially begin or end (but not both) with a hyphen ('-'). You must return the number of strings of length len that match all of the patterns. A digit must be matched with the same digit. A question mark can be matched with any digit. If the pattern ends with a hyphen, the pattern is describing a prefix. Similarly, if the pattern begins with a hyphen it describes a suffix. If there are no hyphens, the matched string must have the same length as the pattern. Said differently, a hyphen matches 0 or more digits.
 

Definition

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

Constraints

-patterns will contain between 1 and 50 elements, inclusive.
-Each element of patterns will contain between 1 and 50 characters, inclusive.
-Each character in patterns will be a digit ('0'-'9'), a question mark ('?'), or a hyphen ('-');
-Each element of patterns will contain at most 1 hyphen, and it must occur at the beginning or the end of the element.
-len will be between 1 and 50, inclusive.
-The return value will be between 0 and 1,000,000,000, inclusive.
-No element of patterns will be "-" (quotes for clarity).
 

Examples

0)
    
{"???"}
3
Returns: 1000
Every 3 digit string is possible.
1)
    
{"9??","??7"}
3
Returns: 10
The first digit must be 9 and the last must be 7.
2)
    
{"9??","??7"}
4
Returns: 0
The patterns say that the string must have length 3.
3)
    
{"9??-","-???7"}
4
Returns: 100
The first pattern says the string begins with a 9 and has at least 3 digits. The second pattern says the string ends with a 7 and has at least 4 digits.
4)
    
{
"??????????????????????????????????????????????????",
"?????????????????????????????????????????????????9",
"?????????????????????????????????????????????????8"
}
50
Returns: 0
5)
    
{
"-?????"
}
4
Returns: 0

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10706&pm=7518

Writer:

AdminBrett

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev

Problem categories:

String Manipulation