LeetCode-Solutions/Python/ambiguous-coordinates.py at master · pythonpeixun/LeetCode-Solutions · GitHub

25 lines (20 loc) · 726 Bytes

# Time: O(n^4)

# Space: O(n)

import itertools

class Solution(object):

def ambiguousCoordinates(self, S):

"""

:type S: str

:rtype: List[str]

"""

def make(S, i, n):

for d in xrange(1, n+1):

left = S[i:i+d]

right = S[i+d:i+n]

if ((not left.startswith('0') or left == '0')

and (not right.endswith('0'))):

yield "".join([left, '.' if right else '', right])

return ["({}, {})".format(*cand)

for i in xrange(1, len(S)-2)

for cand in itertools.product(make(S, 1, i),

make(S, i+1, len(S)-2-i))]

Expand file tree