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#
- Remove the outer parentheses from the input string.
- 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.
- 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.
- Combine every valid x with every valid y, formatting as “(x, y)”.
- 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;
}
};
|
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.