[C++/Java/Python] Solution with Explanation
We can split S to two parts for two coordinates.\nThen we use sub function f to find all possible strings for each coordinate.\n\nIn sub functon f(S)\nif S == "
We can split S to two parts for two coordinates.\nThen we use sub function ```f``` to find all possible strings for each coordinate.\n\n**In sub functon f(S)**\nif S == "": return []\nif S == "0": return [S]\nif S == "0XXX0": return []\nif S == "0XXX": return ["0.XXX"]\nif S == "XXX0": return [S]\nreturn [S, "X.XXX", "XX.XX", "XXX.X"...]\n\nThen we add the product of two lists to result.\n\n**Time complexity**\nO(N^3) with N <= 10\n\nProvement:\n![image](https://s3-lc-upload.s3.amazonaws.com/users/lee215/image_1523920967.png)\n\n\nC++:\n```\n    vector<string> ambiguousCoordinates(string S) {\n        int n = S.size();\n        vector<string> res;\n        for (int i = 1; i < n - 2; ++i) {\n            vector<string> A = f(S.substr(1, i)), B = f(S.substr(i + 1, n - 2 - i));\n            for (auto & a : A) for (auto & b : B) res.push_back("(" + a + ", " + b + ")");\n        }\n        return res;\n    }\n    vector<string> f(string S) {\n        int n = S.size();\n        if (n == 0 || (n > 1 && S[0] == \'0\' && S[n - 1] == \'0\')) return {};\n        if (n > 1 && S[0] == \'0\') return {"0." + S.substr(1)};\n        if (n == 1 || S[n - 1] == \'0\') return {S};\n        vector<string> res = {S};\n        for (int i = 1; i < n; ++i) res.push_back(S.substr(0, i) + \'.\' + S.substr(i));\n        return res;\n    }\n```\n**Java:**\n```\n    public List<String> ambiguousCoordinates(String S) {\n        int n = S.length();\n        List<String> res = new ArrayList();\n        for (int i = 1; i < n - 2; ++i) {\n            List<String> A = f(S.substring(1, i + 1)), B = f(S.substring(i + 1, n - 1));\n            for (String a : A) for (String b : B) res.add("(" + a + ", " + b + ")");\n        }\n        return res;\n    }\n    public List<String> f(String S) {\n        int n = S.length();\n        List<String> res = new ArrayList();\n        if (n == 0 || (n > 1 && S.charAt(0) == \'0\' && S.charAt(n - 1) == \'0\')) return res;\n        if (n > 1 && S.charAt(0) == \'0\') {\n            res.add("0." + S.substring(1));\n            return res;\n        }\n        res.add(S);\n        if (n == 1 || S.charAt(n - 1) == \'0\') return res;\n        for (int i = 1; i < n; ++i) res.add(S.substring(0, i) + \'.\' + S.substring(i));\n        return res;\n    }\n```\n**Python:**\n```\n    def ambiguousCoordinates(self, S):\n        S = S[1:-1]\n        def f(S):\n            if not S or len(S) > 1 and S[0] == S[-1] == \'0\': return []\n            if S[-1] == \'0\': return [S]\n            if S[0] == \'0\': return [S[0] + \'.\' + S[1:]]\n            return [S] + [S[:i] + \'.\' + S[i:] for i in range(1, len(S))]\n        return [\'(%s, %s)\' % (a, b) for i in range(len(S)) for a, b in itertools.product(f(S[:i]), f(S[i:]))]\n```
[]