Skip to content

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<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;
  }
};

 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<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 List.of(s);
    if (s.charAt(0) == '0')
      return List.of("0." + s.substring(1));

    List<String> res = new ArrayList<>(List.of(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