Problem Statement
Uncompress the given string s in the following manner: Find a section that matches the pattern "k(q)" (quotes for clarity only), where k is a single digit, the two parentheses are a matching set, and q is zero or more characters. Replace the entire section with k consecutive occurrences of q. Repeat this process until there are no more such patterns. Return the length of the uncompressed string.
Definition
- Class:
- CompressedString
- Method:
- getLength
- Parameters:
- String
- Returns:
- int
- Method signature:
- int getLength(String s)
- (be sure your method is public)
Constraints
- s will contain between 0 and 50 characters, inclusive.
- s will contain only digits ('0'-'9') and parentheses ('(',')').
- The parentheses in s will be properly matched.
- Each opening parenthesis ('(') in s will be preceded by a digit ('0'-'9').
- The return value will be less than or equal to 2147483647.
Examples
"123"
Returns: 3
"10342(76)"
Returns: 8
The uncompressed string is "10347676" (quotes for clarity only).
"33(562(71(9)))"
Returns: 19
The uncompressed string is "3567979567979567979" (quotes for clarity only).
"0(0)"
Returns: 0
"1(1(1(1(1(1(1(0(1234567890))))))))"
Returns: 0
"9(9(9(6(4(9(9(9(9(9(34))))))))))"
Returns: 2066242608
"4(4(4(4(2(3(4(4(4(2(4(4(4(4(4(4(12))))))))))))))))"
Returns: 1610612736
"9(9(9(9(9(9(9(39(9(9(9(9(9(9(9(9())))))))))))))))"
Returns: 4782969
"9(9(9(9(9(9(9(9(9(9(9(9(9(9(9(9())))))))))))))))"
Returns: 0
"14(4(4(4(2(4(4(4(4(2(4(4(4(4(4(4(7))))))))))))))))"
Returns: 1073741825
"14(4(4(4(2(4(34(4(4(2(4(4(4(4(4(4())))))))))))))))"
Returns: 2049
""
Returns: 0
"0()"
Returns: 0
"1()66(5)"
Returns: 7
"67(333)"
Returns: 22
"9(9(9(8(9(9(9(9(7(9(9(9(9(9(0(6())))))))))))))))"
Returns: 0
"10()6()72838(17(5(7)))15()870()55099(9)2575"
Returns: 313
"16(4)6215(25)728(9337(8))85866883(0685)41()2"
Returns: 123
"1(68(2(12()1)2(062777)68()))18()0442(0)236"
Returns: 146
"23(9238)77646852(80(2)8(5(0)68))64(5741)097(49)"
Returns: 167
"77(07)4(483)397845(2434(4(97())5)9330)70()"
Returns: 168
"386(77)077(2)0(3())7165(0)13()779(11)622()"
Returns: 54
"9()92()588(1())848()246533()1668(05(6)01)4()4"
Returns: 78
"5(2)7(31()9)49()43(6()4)12(9)9()"
Returns: 27
"7591647199()4(1)1539613()87()94"
Returns: 22
"2080605(2)6()3()8(96(4(61)5(4)))"
Returns: 643
"31780526(2(8)061725(67)71533870955)9(2507)1"
Returns: 212
"7(55(1652)85(1)899)128193(689)8586685"
Returns: 231
"435(1418068()39826)23(12)6()7778()"
Returns: 67
"6(5)16()0(4()5401)13(8(2949(4(82(637764)8))))"
Returns: 12176
"2228513755646(741(093(4)9877)0(5145()))"
Returns: 78
"84(67(3)2(097(156()3308294)018696(0377(62)02391)))"
Returns: 1649
"0()998()05(5(116227)309(2)06881)1(9)6342632"
Returns: 241
"200983362160546754408827(97)859(8(75760))"
Returns: 399
"17213(1575)7(20)6471079(3101(1113(14444(365))))"
Returns: 522
"3195843435649(5(9)62(50()352698(3)))10"
Returns: 320
"9(9(9(9(9(9(9(9(9(9)))))))))"
Returns: 387420489
"0(9(9(0)))0"
Returns: 1
"7(7(7(7(7(7(7(7(7(2(2(2(2(2(7)))5(5()))))))))))))"
Returns: 1291315424
"9(9(9(9(9(9(9(9(9(5(1))))))))))"
Returns: 1937102445
"42300929(9(9(09(9(9(9(9(9(1523)))))))))84327483243"
Returns: 1549682703
"9(9(9(9(9(9(9(9(9(8)))))))))"
Returns: 387420489
"6(7(9(9(9(9(9(39(31)13()13(129(2)))))29(223)1))2))"
Returns: 134021832
"2(2)22"
Returns: 4
"3(562(71(9)))232"
Returns: 21
"8(8(8))"
Returns: 64
"3213(3234)2(34(3(3)24))"
Returns: 57
"5(15(15(15(15(15(15(15(15(15(15(15(1))))))))))))"
Returns: 305175780
"9(9(9(9(9(9(9(9(99999999999))))))))"
Returns: 473513931
"9(9(9(9(9(9(9(9(9(999)))))))))"
Returns: 1162261467
"9(3242323234423442349(9(9(9(9(9(9(9(1245)))))))))"
Returns: 1549682118
"2(3(0(1)1))"
Returns: 6
"1()"
Returns: 0
""
Returns: 0
"3()12"
Returns: 2
"9(9(9(9(9(9(9(9(9))))))))"
Returns: 43046721
"9(9(9(1(1(1(1(8(2(8(9(7(9(1234)))))))))))))9()9()"
Returns: 211631616
"9(9(9(9(9(9(9(9(9(11)))))))))"
Returns: 774840978
"9(9(9(9(9(9(9(9(123))))))))"
Returns: 129140163