• Time:O(n^3)
• Space:O(n^3)

## C++

``````class Solution {
public:
vector<string> ambiguousCoordinates(string S) {
vector<string> ans;
S = S.substr(1, S.length() - 2);

for (int i = 1; i < S.length(); ++i)
for (const string& x : splits(S.substr(0, i)))
for (const string& y : splits(S.substr(i)))
ans.push_back('(' + x + ", " + y + ')');

return ans;
}

private:
vector<string> splits(const string& S) {
if (S.empty() || S.length() > 1 && S.front() == '0' && S.back() == '0')
return {};
if (S.back() == '0')
return {S};
if (S.front() == '0')
return {"0." + S.substr(1)};

vector<string> candidates{S};
for (int i = 1; i < S.length(); ++i)
candidates.push_back(S.substr(0, i) + '.' + S.substr(i));
return candidates;
}
};
``````

## JAVA

``````class Solution {
public List<String> ambiguousCoordinates(String S) {
List<String> ans = new ArrayList<>();
S = S.substring(1, S.length() - 1);

for (int i = 1; i < S.length(); ++i)
for (final String x : splits(S.substring(0, i)))
for (final String y : splits(S.substring(i)))
ans.add("(" + x + ", " + y + ")");

return ans;
}

private List<String> splits(final String S) {
if (S.isEmpty() || S.length() > 1 && S.charAt(0) == '0' && S.charAt(S.length() - 1) == '0')
return new ArrayList<>();
if (S.charAt(S.length() - 1) == '0')
return new ArrayList<>(Arrays.asList(S));
if (S.charAt(0) == '0')
return new ArrayList<>(Arrays.asList("0." + S.substring(1)));

List<String> res = new ArrayList<>(Arrays.asList(S));
for (int i = 1; i < S.length(); ++i)
res.add(S.substring(0, i) + "." + S.substring(i));
return res;
}
}
``````

## Python

``````class Solution:
def ambiguousCoordinates(self, S: str) -> List[str]:
def splits(S: str) -> List[str]:
if not S or len(S) > 1 and S[0] == S[-1] == '0':
return []
if S[-1] == '0':
return [S]
if S[0] == '0':
return [S[0] + '.' + S[1:]]
return [S] + [S[:i] + '.' + S[i:] for i in range(1, len(S))]

ans = []
S = S[1:-1]

for i in range(1, len(S)):
for x in splits(S[:i]):
for y in splits(S[i:]):
ans.append('(%s, %s)' % (x, y))

return ans
``````