[Python] product solution with correct complexity, explained
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 d
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`.\n\nThen we split `S` into all possible  ways, for each part generate all numbers and then choose all pairs of numbers. \n\n#### Complexity\nThere 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)`.\n\n```python\nclass Solution:\n    def ambiguousCoordinates(self, S):\n        def generate(s):\n            ans = []\n            if s == "0" or s[0] != "0": ans.append(s)\n            for i in range(1, len(s)):\n                if (s[:i] == "0" or s[0] != "0") and s[-1] != "0":\n                    ans.append(s[:i] + "." + s[i:])\n            return ans\n        \n        n, ans = len(S), []\n        for i in range(2, n-1):\n            cand_l, cand_r = generate(S[1:i]), generate(S[i:-1])     \n            for l, r in product(cand_l, cand_r):\n                ans.append("(" + l + ", " + r + ")")\n                \n        return ans\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]