BuffaloBuffaloBuffalo
SRM 723 · 2017-11-17 · by cgy4ever
SRM 723 · 2017-11-17 · by cgy4ever · Dynamic Programming
Problem Statement
Problem Statement
Did you know that "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo." is a grammatically correct sentence in American English?
We say that a string A is produced by interleaving strings B and C if we can color each character of A either red or blue in such a way that the red characters, in order, produce the string B and the blue characters, in order, produce the string C. For example, each of the strings "dogcat", "catdog", "cadogt" and "cdaotg" can be obtained by interleaving the strings "cat" and "dog".
Interleaving more than two strings is defined in the same way. For example, the string "aaabcbcbc" can be obtained by interleaving three copies of the string "abc".
A string is called good if it can be obtained by interleaving one or more copies of the string "buffalo". For example, the strings "buffalo", "bbuuffaalloo", and "buffalobuffalobuffalo" are good, but "buffaloolaffub" and "bubufffflaaloo" are not good.
A pattern is a string that consists of lowercase letters and question marks ('?'). We say that a string S of lowercase letters matches a pattern P if we can obtain S from P by replacing each '?' by some lowercase letter. Different question marks may be replaced by different letters. For example, the string "abcde" matches the pattern "a?c?e".
You are given aString pattern that contains a pattern.
Let X be the number of good strings that match pattern.
Compute and return the value X modulo (10^9 + 7).
We say that a string A is produced by interleaving strings B and C if we can color each character of A either red or blue in such a way that the red characters, in order, produce the string B and the blue characters, in order, produce the string C. For example, each of the strings "dogcat", "catdog", "cadogt" and "cdaotg" can be obtained by interleaving the strings "cat" and "dog".
Interleaving more than two strings is defined in the same way. For example, the string "aaabcbcbc" can be obtained by interleaving three copies of the string "abc".
A string is called good if it can be obtained by interleaving one or more copies of the string "buffalo". For example, the strings "buffalo", "bbuuffaalloo", and "buffalobuffalobuffalo" are good, but "buffaloolaffub" and "bubufffflaaloo" are not good.
A pattern is a string that consists of lowercase letters and question marks ('?'). We say that a string S of lowercase letters matches a pattern P if we can obtain S from P by replacing each '?' by some lowercase letter. Different question marks may be replaced by different letters. For example, the string "abcde" matches the pattern "a?c?e".
You are given a
Constraints
- pattern will contain between 1 and 100 characters, inclusive.
- Each character in pattern will be a lowercase English letter ('a' - 'z') or '?'.
Examples
0)
"buffa????ffalo" Returns: 6
There are 6 good strings that match the given pattern: "buffalobuffalo" "buffalbouffalo" "buffalbuoffalo" "buffablouffalo" "buffabluoffalo" "buffabuloffalo"
1)
"buffal????????" Returns: 7
2)
"b??????b??????b??????b??????" Returns: 1
The only good string is "buffalobuffalobuffalobuffalo".
3)
"???????????????????????????????????" Returns: 420429295
Don't forget mod.
4)
"x" Returns: 0
Submissions are judged against all 112 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BuffaloBuffaloBuffalo with a public method int count(string pattern) · 112 test cases · 2 s / 256 MB per case