BinaryRandomString | Topcoder Archive

Problem Statement

You are given a String baseString containing 0's, 1's, and '?'s. Each '?' represents an unknown character. The string was randomly generated, so each '?' could be either '0' or '1' with equal probability.

You are also given a String pattern, and you must determine whether or not it is a substring of baseString. You may request the identities of unknown '?' characters one at a time until you can determine the answer. Return the expected number of requests necessary if you use an optimal strategy.

Definition

Class:: BinaryRandomString
Method:: checkPattern
Parameters:: String, String
Returns:: double
Method signature:: double checkPattern(String baseString, String pattern)
(be sure your method is public)

Notes

Your return value must have an absolute or relative error less than 1e-9.

Constraints

baseString will contain between 1 and 10 characters, inclusive.
baseString will consist of only characters '0' (zero), '1' (one), and '?'.
pattern will contain between 1 and 10 characters, inclusive.
pattern will consist of only characters '0' (zero) and '1' (one).

Examples

```
"???"
```
```
"00"
```
```
Returns: 1.75
```
We should request the second character. It can be either '1' or '0' with equal probability. In the first case we can immediately report that pattern is not a substring of baseString. Otherwise we should request the first character. If it is '0', we can report that pattern is a substring of baseString. If it is '1', then we should request the third character. The expected number of requests is 0.5*1+0.5*(0.5*2+0.5*3)=1.75
```
"1?0"
```
```
"01"
```
```
Returns: 0.0
```
baseString can be either "100" or "110". pattern is not a substring of either possibility.
```
"??11?"
```
```
"011"
```
```
Returns: 1.5
```
```
"???11??0??"
```
```
"0011"
```
```
Returns: 2.84375
```
```
"??????????"
```
```
"0011"
```
```
Returns: 4.953125
```

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.