TopCoder Statistics - Problem Statement

Problem Statement

Regular expressions are simple but powerful ways of describing patterns for strings of symbols. We will restrict our attention to describing binary strings using only the special symbol * which means "zero or more occurrences". So our simple regular expression will be a sequence of characters, all of which are '0', '1' or '*'. Furthermore, each '*' will be preceded by a '0' or a '1' and will apply to that single character.

For example, "01*00*" describes all strings that start with '0', then have zero or more '1's, then have a '0', and then have zero or more '0's. The shortest string that satisfies this description is "00".

Create a class Regulars that contains a method stringCt that is given a simple regular expression regex and an int maxLen and that returns the number of distinct strings that satisfy regex and contain between 0 and maxLen characters, inclusive.

Definition

Class:: Regulars
Method:: stringCt
Parameters:: String, int
Returns:: long
Method signature:: long stringCt(String regex, int maxLen)
(be sure your method is public)

Constraints

regex will contain between 1 and 50 characters, inclusive.
Each character in regex will be '0' (zero), '1' (one), or '*'.
Each '*' in regex will be immediately preceded by '0' or '1'.
maxLen will be between 1 and 50, inclusive.

Examples

"0*"

5

Returns: 6

"","0","00","000","0000","00000" are the legal strings.
"01*1*1*"

3

Returns: 3

"0","01","011" are the legal strings.
"0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*"

50

Returns: 1125899906842623
"0*0*011*0*0"

3

Returns: 1
"0*0*011*0*0"

4

Returns: 4
"0*010*011*0*1*"

12

Returns: 957
"0*1*0*1*0*1*0*1*0*1*0*1*0*1*011*0*1*0*1*0*1*0*1*0*"

50

Returns: 877940640367245
"0*011*111*011*0*10*010000*1*10*10*10*0*000*11*"

1

Returns: 0
"1*1110*01*010110*10*0101*0*01*01*01*1*010011*"

21

Returns: 1
"0*1010*1*00*11*01*01*111101*1*1*0*01*0*0*0*1*100*"

50

Returns: 89532995271
"0*0*1*0110*0*00*10*0*0*0*001*1*100110*0*1*00*1000"

38

Returns: 3404115
"1*0*0*10*0100*1*011*11*010*01*1*1*1*10*10*1*10*01"

29

Returns: 7161556
"0*01*11*0*1*1*"

3

Returns: 4
"0*01*11*0*1*1*"

4

Returns: 11
"0*01*11*0*1*1*"

5

Returns: 25
"0*0*01*11*0*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*1*"

4

Returns: 11
"1*1110*01*010110*10*0101*0*01*01*01*1*010011*"

22

Returns: 12
"1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*0*1*"

50

Returns: 1125899906842623
"11*1*0000*0111*1*0*1001010111*1110100*111*010*00*"

26

Returns: 0
"11*1*0000*0111*1*0*1001010111*1110100*111*010*00*"

27

Returns: 1
"11*1*0000*0111*1*0*1001010111*1110100*111*010*00*"

28

Returns: 9
"1*01*0*01*10000*110*01*0*1*110*110*1*0*0011100*"

19

Returns: 1
"1*01*0*01*10000*110*01*0*1*110*110*1*0*0011100*"

18

Returns: 0
"0*1*1*0*01*01*1011*00*1110*100*1*1*000100*0111*0"

6

Returns: 0
"1*1*0*1*01*"

1

Returns: 1
"1*1*0*1*01*"

11

Returns: 781
"0101010*1010101*0101110010101*1010101101*01010101"

50

Returns: 715

Statistics

Problem Statement for "Regulars"

Problem Statement

Definition

Constraints

Examples