Problem

We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)". Then, we removed all commas, decimal points, and spaces and ended up with the string s.

  • For example, "(1, 3)" becomes s = "(13)" and "(2, 0.5)" becomes s = "(205)".

Return a list of strings representing all possibilities for what our original coordinates could have been.

Our original representation never had extraneous zeroes, so we never started with numbers like "00", "0.0", "0.00", "1.0", "001", "00.01", or any other number that can be represented with fewer digits. Also, a decimal point within a number never occurs without at least one digit occurring before it, so we never started with numbers like ".1".

The final answer list can be returned in any order. All coordinates in the final answer have exactly one space between them (occurring after the comma.)

Examples

Example 1:

1
2

Input: s = "(123)"
Output: ["(1, 2.3)","(1, 23)","(1.2, 3)","(12, 3)"]

Example 2:

1
2
3

Input: s = "(0123)"
Output: ["(0, 1.23)","(0, 12.3)","(0, 123)","(0.1, 2.3)","(0.1, 23)","(0.12, 3)"]
Explanation: 0.0, 00, 0001 or 00.01 are not allowed.

Example 3:

1
2

Input: s = "(00011)"
Output: ["(0, 0.011)","(0.001, 1)"]

Constraints:

  • 4 <= s.length <= 12
  • s[0] == '(' and s[s.length - 1] == ')'.
  • The rest of s are digits.

Solution

Method 1 – Enumeration and String Partitioning

Intuition

The key idea is to try every possible way to split the digits (excluding the parentheses) into two non-empty parts, representing the x and y coordinates. For each part, generate all valid representations by possibly inserting a decimal point, ensuring no leading/trailing zeros unless the number is exactly “0”. Combine all valid pairs to form the answer.

Approach

  1. Remove the outer parentheses from the input string.
  2. For every possible split between the digits (from index 1 to n-1), treat the left part as x and the right part as y.
  3. For each part, generate all valid numbers by:
  • Keeping it as an integer if valid (no leading zeros unless it’s “0”).
  • Inserting a decimal point at every possible position (not at the ends), ensuring no trailing zeros after the decimal and no leading zeros before it.
  1. Combine every valid x with every valid y, formatting as “(x, y)”.
  2. Return the list of all such combinations.

C++

 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
30
31
32
33

class Solution {
public:
   vector<string> ambiguousCoordinates(string s) {
      vector<string> ans;
      string digits = s.substr(1, s.size() - 2);
      int n = digits.size();
      for (int i = 1; i < n; ++i) {
        vector<string> left = gen(digits.substr(0, i));
        vector<string> right = gen(digits.substr(i));
        for (const string& l : left) {
           for (const string& r : right) {
              ans.push_back("(" + l + ", " + r + ")");
           }
        }
      }
      return ans;
   }
private:
   vector<string> gen(const string& s) {
      vector<string> res;
      int n = s.size();
      if (n == 1 || (s[0] != '0')) res.push_back(s);
      for (int i = 1; i < n; ++i) {
        string intPart = s.substr(0, i), fracPart = s.substr(i);
        if ((intPart.size() > 1 && intPart[0] == '0') || fracPart.back() == '0') continue;
        res.push_back(intPart + "." + fracPart);
      }
      if (n > 1 && s[0] == '0') {
        if (s.back() != '0') res.push_back(s.substr(0,1) + "." + s.substr(1));
      }
      return res;
   }
};

Go

 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
30
31
32
33
34
35
36

type Solution struct{}

func (Solution) AmbiguousCoordinates(s string) []string {
   ans := []string{}
   digits := s[1 : len(s)-1]
   n := len(digits)
   for i := 1; i < n; i++ {
      left := gen(digits[:i])
      right := gen(digits[i:])
      for _, l := range left {
        for _, r := range right {
           ans = append(ans, "("+l+", "+r+")")
        }
      }
   }
   return ans
}

func gen(s string) []string {
   n := len(s)
   res := []string{}
   if n == 1 || s[0] != '0' {
      res = append(res, s)
   }
   for i := 1; i < n; i++ {
      intPart, fracPart := s[:i], s[i:]
      if (len(intPart) > 1 && intPart[0] == '0') || fracPart[len(fracPart)-1] == '0' {
        continue
      }
      res = append(res, intPart+"."+fracPart)
   }
   if n > 1 && s[0] == '0' && s[n-1] != '0' {
      res = append(res, s[:1]+"."+s[1:])
   }
   return res
}

Java

 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
30
31

class Solution {
   public List<String> ambiguousCoordinates(String s) {
      List<String> ans = new ArrayList<>();
      String digits = s.substring(1, s.length() - 1);
      int n = digits.length();
      for (int i = 1; i < n; i++) {
        List<String> left = gen(digits.substring(0, i));
        List<String> right = gen(digits.substring(i));
        for (String l : left) {
           for (String r : right) {
              ans.add("(" + l + ", " + r + ")");
           }
        }
      }
      return ans;
   }
   private List<String> gen(String s) {
      List<String> res = new ArrayList<>();
      int n = s.length();
      if (n == 1 || s.charAt(0) != '0') res.add(s);
      for (int i = 1; i < n; i++) {
        String intPart = s.substring(0, i), fracPart = s.substring(i);
        if ((intPart.length() > 1 && intPart.charAt(0) == '0') || fracPart.charAt(fracPart.length() - 1) == '0') continue;
        res.add(intPart + "." + fracPart);
      }
      if (n > 1 && s.charAt(0) == '0' && s.charAt(n - 1) != '0') {
        res.add(s.substring(0, 1) + "." + s.substring(1));
      }
      return res;
   }
}

Kotlin

 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
30
31

class Solution {
   fun ambiguousCoordinates(s: String): List<String> {
      val ans = mutableListOf<String>()
      val digits = s.substring(1, s.length - 1)
      for (i in 1 until digits.length) {
        val left = gen(digits.substring(0, i))
        val right = gen(digits.substring(i))
        for (l in left) {
           for (r in right) {
              ans.add("($l, $r)")
           }
        }
      }
      return ans
   }
   private fun gen(s: String): List<String> {
      val res = mutableListOf<String>()
      val n = s.length
      if (n == 1 || s[0] != '0') res.add(s)
      for (i in 1 until n) {
        val intPart = s.substring(0, i)
        val fracPart = s.substring(i)
        if ((intPart.length > 1 && intPart[0] == '0') || fracPart.last() == '0') continue
        res.add("$intPart.$fracPart")
      }
      if (n > 1 && s[0] == '0' && s.last() != '0') {
        res.add("${s[0]}.${s.substring(1)}")
      }
      return res
   }
}

Python

 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

class Solution:
   def ambiguousCoordinates(self, s: str) -> list[str]:
      def gen(x: str) -> list[str]:
        n = len(x)
        res: list[str] = []
        if n == 1 or x[0] != '0':
           res.append(x)
        for i in range(1, n):
           int_part, frac_part = x[:i], x[i:]
           if (len(int_part) > 1 and int_part[0] == '0') or frac_part[-1] == '0':
              continue
           res.append(int_part + '.' + frac_part)
        if n > 1 and x[0] == '0' and x[-1] != '0':
           res.append(x[0] + '.' + x[1:])
        return res

      digits = s[1:-1]
      ans: list[str] = []
      for i in range(1, len(digits)):
        left = gen(digits[:i])
        right = gen(digits[i:])
        for l in left:
           for r in right:
              ans.append(f"({l}, {r})")
      return ans

Rust

 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
30
31
32
33
34
35

impl Solution {
   pub fn ambiguous_coordinates(s: String) -> Vec<String> {
      fn gen(s: &str) -> Vec<String> {
        let n = s.len();
        let mut res = Vec::new();
        if n == 1 || !s.starts_with('0') {
           res.push(s.to_string());
        }
        for i in 1..n {
           let int_part = &s[..i];
           let frac_part = &s[i..];
           if (int_part.len() > 1 && int_part.starts_with('0')) || frac_part.ends_with('0') {
              continue;
           }
           res.push(format!("{}.{}", int_part, frac_part));
        }
        if n > 1 && s.starts_with('0') && !s.ends_with('0') {
           res.push(format!("{}.{}", &s[..1], &s[1..]));
        }
        res
      }
      let digits = &s[1..s.len()-1];
      let mut ans = Vec::new();
      for i in 1..digits.len() {
        let left = gen(&digits[..i]);
        let right = gen(&digits[i..]);
        for l in &left {
           for r in &right {
              ans.push(format!("({}, {})", l, r));
           }
        }
      }
      ans
   }
}

Complexity

  • ⏰ Time complexity: O(n^3) — For each split, generate all valid decimal placements for both sides.
  • 🧺 Space complexity: O(n^3) — For storing all possible coordinate strings.