DeserializeSequence
SRM 230 · 2005-02-08 · by AdminBrett
SRM 230 · 2005-02-08 · by AdminBrett · Dynamic Programming
Problem Statement
Problem Statement
Given a sequence of positive integers in nondescending order you can make a string by concatenating the sequence elements together. For example, the sequence [1,1,13,934] could become the string "01113934". Given a String str containing digits return how many distinct nondescending sequences could have produced str. Two sequences are distinct if they differ in some position, or have different lengths. When put into str, the sequence element could have been padded with leading zeros. For example, [1,2] could become "12", "00010002", "010002" as well as numerous other possible strings. You should assume the integers in the original sequence were between 1 and 1000000 inclusive.
Constraints
- str must contain between 1 and 50 characters inclusive.
- Each character of str must be a digit ('0' - '9').
Examples
0)
"1234" Returns: 5
The 5 possible sequences are: [1,2,3,4] [1,2,34] [1,234] [1234] [12,34]
1)
"000000000001" Returns: 1
[1] is the only possible sequence here.
2)
"1000000000000" Returns: 0
No possible sequences.
3)
"9876543210" Returns: 5
4)
"11111111111111111111111111111111111111111111111111" Returns: 9192
Submissions are judged against all 53 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DeserializeSequence with a public method int howMany(string str) · 53 test cases · 2 s / 256 MB per case