Problem statement

https://leetcode.com/problems/ambiguous-coordinates/

Solution

Let us create function generate(s), which generate all possible candidates for string s: we need to check number without dot and also all possible ways to put dot inside. We need to check the condition our original representation never had extraneous zeroes, so we check that if some number starts with 0, it should be equal to 0.

Then we split S into all possible ways, for each part generate all numbers and then choose all pairs of numbers.

Complexity

There is O(n) ways to split string S into two parts. Overall time and space complexity will be O(n^4), for example for string "(" + "1"*n + ")", number of ways will be approximately n^3/6, each of them have length O(n).

class Solution:
    def ambiguousCoordinates(self, S):
        def generate(s):
            ans = []
            if s == "0" or s[0] != "0": ans.append(s)
            for i in range(1, len(s)):
                if (s[:i] == "0" or s[0] != "0") and s[-1] != "0":
                    ans.append(s[:i] + "." + s[i:])
            return ans
        
        n, ans = len(S), []
        for i in range(2, n-1):
            cand_l, cand_r = generate(S[1:i]), generate(S[i:-1])     
            for l, r in product(cand_l, cand_r):
                ans.append("(" + l + ", " + r + ")")
                
        return ans