Approach #1: Cartesian Product [Accepted]

Intuition and Algorithm

For each place to put the comma, we separate the string into two fragments. For example, with a string like "1234", we could separate it into fragments "1" and "234", "12" and "34", or "123" and "4".

Then, for each fragment, we have a choice of where to put the period, to create a list make(...) of choices. For example, "123" could be made into "1.23", "12.3", or "123".

Because of extranneous zeroes, we should ignore possibilities where the part of the fragment to the left of the decimal starts with "0" (unless it is exactly "0"), and ignore possibilities where the part of the fragment to the right of the decimal ends with "0", as these are not allowed.

Note that this process could result in an empty answer, such as for the case S = "(000)".

Complexity Analysis

  • Time Complexity: , where is the length S. We evaluate the sum .

  • Space Complexity: , to store the answer.


Analysis written by: @awice.