You are given a compressed word that is in one of the following three forms:
- A single character 'A' or 'B'. In this case, the uncompressed word is equal to the compressed one.
- A string formatted as "ST" (quotes for clarity), where S and T are each compressed words. To uncompress a word of this form, uncompress S and T and return their concatenation.
- A string formatted as "(X,S)" (quotes for clarity), where X is a digit between 1 and 9, inclusive, and S is a compressed word. To uncompress a word of this form, uncompress S and return the concatenation of X copies of that uncompressed word.
For example, "(2,A(3,AB))" uncompresses to "AABABABAABABAB", and "A(2,B)" uncompresses to "ABB". The latter example is uncompressed as follows:
- "A(2,B)" is in form 2, where S = "A" and T= "(2,B)". S is in form 1 so it's already uncompressed. Next, we uncompress T.
- "(2,B)" is in form 3, where X = 2 and S = "B". S is in form 1 so it's already uncompressed. We concatenate 2 copies of it to get "BB".
- We concatenate S and T from step 1 to get "ABB".
A maximal continuous sequence of the same letter in a word is called a block. For example, "AABAAABBBAA" contains 5 blocks: AA, B, AAA, BBB, and AA.
You are given a compressed word. Return the number of blocks in the uncompressed form of the word.
|