|
| 1 | +# Time: O(n^4) |
| 2 | +# Space: O(n) |
| 3 | + |
| 4 | +# We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". |
| 5 | +# Then, we removed all commas, decimal points, and spaces, |
| 6 | +# and ended up with the string S. |
| 7 | +# Return a list of strings representing all possibilities for |
| 8 | +# what our original coordinates could have been. |
| 9 | +# |
| 10 | +# Our original representation never had extraneous zeroes, |
| 11 | +# so we never started with numbers like |
| 12 | +# "00", "0.0", "0.00", "1.0", "001", "00.01", |
| 13 | +# or any other number that can be represented with less digits. |
| 14 | +# Also, a decimal point within a number never occurs without |
| 15 | +# at least one digit occuring before it, |
| 16 | +# so we never started with numbers like ".1". |
| 17 | +# |
| 18 | +# The final answer list can be returned in any order. |
| 19 | +# Also note that all coordinates in the final answer |
| 20 | +# have exactly one space between them |
| 21 | +# (occurring after the comma.) |
| 22 | +# |
| 23 | +# Example 1: |
| 24 | +# Input: "(123)" |
| 25 | +# Output: ["(1, 23)", "(12, 3)", "(1.2, 3)", "(1, 2.3)"] |
| 26 | +# Example 2: |
| 27 | +# Input: "(00011)" |
| 28 | +# Output: ["(0.001, 1)", "(0, 0.011)"] |
| 29 | +# Explanation: |
| 30 | +# 0.0, 00, 0001 or 00.01 are not allowed. |
| 31 | +# Example 3: |
| 32 | +# Input: "(0123)" |
| 33 | +# Output: ["(0, 123)", "(0, 12.3)", "(0, 1.23)", "(0.1, 23)", "(0.1, 2.3)", "(0.12, 3)"] |
| 34 | +# Example 4: |
| 35 | +# Input: "(100)" |
| 36 | +# Output: [(10, 0)] |
| 37 | +# Explanation: |
| 38 | +# 1.0 is not allowed. |
| 39 | +# |
| 40 | +# Note: |
| 41 | +# - 4 <= S.length <= 12. |
| 42 | +# - S[0] = "(", S[S.length - 1] = ")", and the other elements in S are digits. |
| 43 | + |
| 44 | +import itertools |
| 45 | + |
| 46 | +try: |
| 47 | + xrange # Python 2 |
| 48 | +except NameError: |
| 49 | + xrange = range # Python 3 |
| 50 | + |
| 51 | + |
| 52 | +class Solution(object): |
| 53 | + def ambiguousCoordinates(self, S): |
| 54 | + """ |
| 55 | + :type S: str |
| 56 | + :rtype: List[str] |
| 57 | + """ |
| 58 | + def make(S, i, n): |
| 59 | + for d in xrange(1, n+1): |
| 60 | + left = S[i:i+d] |
| 61 | + right = S[i+d:i+n] |
| 62 | + if ((not left.startswith('0') or left == '0') |
| 63 | + and (not right.endswith('0'))): |
| 64 | + yield "".join([left, '.' if right else '', right]) |
| 65 | + |
| 66 | + return ["({}, {})".format(*cand) |
| 67 | + for i in xrange(1, len(S)-2) |
| 68 | + for cand in itertools.product(make(S, 1, i), |
| 69 | + make(S, i+1, len(S)-2-i))] |
0 commit comments