# 816. Ambiguous Coordinates

• Time: $O(n^3)$
• Space: $O(n^3)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public: vector ambiguousCoordinates(string S) { vector 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 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 candidates{S}; for (int i = 1; i < S.length(); ++i) candidates.push_back(S.substr(0, i) + '.' + S.substr(i)); return candidates; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public List ambiguousCoordinates(String S) { List 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 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 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 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